In the fretting wear process of alloy steel, the in-situ formation of lubricative oxide layers on the surface significantly influences wear resistance. Ultrasonic surface rolling processing (USRP) can fabricate a nanogradient structure on the surface of 40CrNiMoA steel, which exhibits unique tribo-oxidation behavior during fretting wear. However, the underlying regulatory mechanism remains unclear. To address this, this study prepared a nanogradient structure via USRP and systematically investigated the interplay between frictional behaviour, microstructural evolution and tribo-oxidation through fretting wear tests. The study elucidates the micro-mechanism by which the nano-gradient structure regulates tribological oxidation and enhances wear resistance through the synergistic effects of grain refinement and dislocation proliferation. The results demonstrate that the nanogradient structure enhances the material's shear resistance and promotes the rapid formation of a uniform and stable oxide layer (The oxide layer had already formed after 30   s of fretting wear, with an oxide layer thickness that was 169   nm thicker than the substrate.). Meanwhile, the coarsening of nanocrystals can effectively suppress the persistent oxidation of the surface microstructure, preventing the formation of oxides and thereby avoiding brittle failure, maintaining the oxide layer at a nanoscale thickness.