Vapor condensation on solid surfaces plays a crucial role across a wide range of industrial applications. Recent advances of nanotechnology have made possible the manipulation of the condensation process through the control of surface structures. In this work, we study vapor condensation on hydrophobic surfaces patterned with microscale pillars. The critical nuclei, the activation barriers, and the minimum energy paths are computed using the climbing string method. The effects of pillar height, interpillar spacing, the level of supersaturation, and the intrinsic wettability of the solid surface on the nucleation process are investigated. Two nucleation scenarios are obtained from the computation. In the case of high pillar, narrow interpillar spacing, low supersaturation, and/or low surface wettability, the critical nucleus prefers the suspended Cassie state; otherwise, it prefers the "impaled Wenzel state. A comparison of the nucleation barrier with that on a flat surface of the same material reveals that vapor condensation is inhibited by the microstructures in the former case, while enhanced in the latter case. The critical values of the pillar height, the interpillar spacing, and the supersaturation at which the critical nucleus changes from the Cassie state to the Wenzel state are identified from the phase diagram of the critical nucleus. It is found that the dependence of the critical interpillar spacing on the supersaturation follows closely the curve of the critical radii in a homogeneous nucleation. The relaxation dynamics of the condensate after the critical nucleus is formed is computed by solving the steepest descent equation. It is observed that when the pillar is low and/or the interpillar spacing is wide, a condensate initially in the Cassie state may evolve into the Wenzel state during the relaxation.