Magnesium alloys with long-period stacking ordered (LPSO) structures are known for their impressive static mechanical strength, but the consistent occurrence of slip-cracking along the LPSO lamellae, which do not effectively impede the movement of basal dislocations, has prompted concerns about their very high cycle fatigue (VHCF) performance. In this study, an extruded Mg-Gd-Zn-Zr alloy was developed, showcasing exceptional VHCF resistance due to its bimodal structure comprising fine grains and coarse grains consisting of curved LPSO lamellae. The investigation on the crack initiation mechanism revealed that slip-induced cracking predominantly occurs in fine-grained regions rather than in the interior of coarse grains. The extrusion process aligns the basal planes of most coarse grains parallel to the axial direction, and the presence of curved LPSO lamellae acts as barriers to the movement of basal dislocations, thereby effectively increasing the threshold for slip-cracking along the basal plane. Consequently, fatigue damage manifests in the form of slip bands and micro-cracks within the interior of fine grains, ultimately resulting in fatigue crack initiation, propagation and final fracture.