This paper studies the fatigue properties and fracture behavior of as-extruded Mg-6Zn-0.5Zr and Mg-10Gd-3Y-0.5Zr alloys before and after shot peening. Compared to Mg-6Zn-0.5Zr alloy, Mg-10Gd-3Y-0.5Zr alloy shows higher optimal Almen intensity, and possesses a broader process window. The stress-controlled rotating bending fatigue property improvement for Mg-10Gd-3Y-0.5Zr alloy by shot peening is significantly superior to that of Mg-6Zn-0.5Zr alloy. With the increase in peening (Almen) intensity, the fatigue crack nucleation site of Mg-6Zn-0.5Zr alloy under stress control shifted from the surface to subsurface, and then back to the surface again. Meanwhile, a significantly higher number of fatigue crack initiation sites can be seen as a consequence of overpeening. However, the fatigue cracks of the peened Mg-10Gd-3Y-0.5Zr alloy initiated subsurface at all Almen intensities, showing unchanged crack initiation location with the increase in Almen intensity. The observed phenomenon is related to differences between the two alloys both in the deformation mechanisms during shot peening and the residual stress relaxation mechanisms during subsequent fatigue process. Namely, at present test conditions such as Almen intensity range and high cycle fatigue stress, in the Mg-6Zn-0.5Zr alloy twinning dominates deformation during shot peening and detwinning during fatigue. Comparatively, dislocation slip dominates deformation in both shot peening and fatigue process in the Mg-10Gd-3Y-0.5Zr alloy.