Magnesium alloys have garnered significant attention in aerospace and automotive industries due to their low density and high specific strength. However, their low surface hardness and strength lead to severe plastic deformation and wear failure when employed as sliding friction components, substantially limiting their tribological applications. This study fabricated gradient nano-heterostructures on AZ91D magnesium alloy surfaces through a combined laser melting (LM) and ultrasonic shot peening (USSP) process. The formation mechanisms of these gradient structures were elucidated using XRD, EBSD, and TEM characterization. Subsequent evaluations of hardness, nanoindentation, and tribological properties revealed the influence of nano-heterostructures on the mechanical and wear performance of AZ91D magnesium alloy. The results reveal that the modified surface (Sample LU) comprises four distinct regions: (1) a nanocrystalline zone (~194 μm, grain size refined to ~6   nm via twin-dislocation interactions); (2) a columnar crystal zone (194-395 μm); (3) a recovered microcrystalline zone (395-600 μm) and (4) the substrate. The uniformly distributed nanograins within the gradient nano-heterostructure significantly enhanced surface hardness and elastic modulus, substantially improving resistance to plastic deformation during friction. Concurrently, nanoscale grain boundaries facilitated accelerated oxygen diffusion, promoting the formation of continuous MgO tribofilms. Synergistically, the graded subsurface structure effectively suppressed crack initiation and propagation. These mechanisms collectively mitigated abrasive wear (through oxide-mediated surface protection), adhesive wear (via reduced metal-to-metal contact), and delamination wear (by crack arrest at heterogeneous interfaces). This work elucidates the intrinsic mechanism by which the LM-USSP hybrid process enhances wear resistance through surface nano-crystallization and gradient microstructural strengthening, providing novel insights for designing high-performance magnesium alloys in tribological systems.