High-frequency impacting and rolling was applied on AZ31B magnesium alloy to obtain a gradient nano-structured surface. Surface characteristics were experimentally investigated, and the nanocrystallization mechanism is discussed in detail. Results showed that the gradient nano-structure with the characteristics of work hardening, compressive residual stress and a smooth surface was induced on the treated surface. Grains on the top surface were generally refined to around 20 nm. Twins, dislocations and dynamic recrystallization dominated the grain refinement process. Fatigue strength of the treated specimens corresponding to 107 cycles was increased by 28.6% compared to that of the as-received specimens. The work hardened layer induced by high-frequency impacting and rolling is the major reason to improve fatigue life.