Double-side ultrasonic shot peening (USSP) was performed on a commercial-purity Zr plate with 2 mm in thickness. The effects of USSP on microstructure evolution and fatigue crack growth (FCG) behavior were investigated. Microstructure evolution was characterized by optical microscopy, laser confocal microscope, electron back-scatter diffraction, transmission electron microscope, and X-ray diffractometer. FCG tests were carried out using compact tension samples, the fracture morphology and crack growth path were analyzed accordingly. The results show that a refined surface gradient structure with compressive residual stress of about 250 μm in depth is formed after USSP treatment. The USSPed samples exhibit higher strength and surface roughness than the as-received samples. Notably, the fatigue crack growth life of USSP-8 min and USSP-12 min samples is increased by 28.1% and 50.9% compared to that of the as-received samples. The USSP treatment helps to improve the resistance to fatigue crack propagation, which in turn reduces the fatigue crack growth rate to a certain extent. The enhancement of the FCG performance can be ascribed to the combined effects of the compressive residual stress and the conspicuous grain refinement. Compressive residual stress enhances the crack closure effect and decreases the effective stress ratio. Meanwhile, grain refinement increases the fraction of grain boundary and decreases the cyclic plastic zone size, which is beneficial for crack growth resistance.