A nanostructured surface layer was fabricated on magnesium alloy AZ91D by using the high-energy impact technique (HEIT). With the help of transmission electron microscope (TEM) and high-resolution transmission electron microscope (HRTEM), the microstructure features of the surface layer were systematically observed and characterized in different stages of microstructure evolution. The result revealed the mechanism of grain refinement and strain accommodation. The process of grain refinement, accompanied by an increase in strain in the surface layer, resulted from several processes. The onset of {01 (1) over bar2} deformation twinning and the intersection with {10 (1) over bar1} twins system are one of them. The operation of < 1 (1) over bar 20 > (0001) basal slip and < 1 (1) over bar 23 > (1 (1) over bar 02)/(0 (1) over bar 12) pyramidal slip led to the formation of dislocation cells and low-angle dislocation boundaries. The successive subdivision of grains to a finer scale resulted in the formation of highly disoriented nanocrystalline grains. The mechanism of grain refinement was interpreted in terms of the structural subdivision of grains together with dynamic recrystallization. The minimum size of such refined grains was about 40 nm.