By means of supersonic fine particles bombarding (SFPB),a nanostructured surface layer up to 15 μm was fabricated on a 45 steel plate with ferrite and pearlite phases. To reveal the grain refinement mechanism of SFPB-treated 45 steel,microstructure features of various sections in the treated surface were systematically characterized by X-ray diffraction (XRD),scanning electron microscopy (SEM) and transmission electron microscopy (TEM). Grain size increases with an increase of depth from the treated surface. Plastic deformation and grain refinement processes are accompanied by an increase in strain. Plastic deformation in the proeutectoid ferrite phases has precedence over the pearlite phases. Grain refinement in the ferrite phases involves: the onset of dislocation lines (Dls),dislocation tangles (DTs) and dense dislocation walls (DDWs) in the original grains; the formation of fine lamellar and roughly equiaxed cells separated by DDWs; by dislocation annihilation and rearrangement,the transformation of DDWS into subboundaries and boundaries and the formation of submicron grains or subgrains; the successive subdivision of grains to finer and finer scale,resulting in the formation of highly misoriented nano-grains. By contrast,eutectoid cementite phase accommodated strain in a sequence as follows: onset of elongated,bended and shear deformation under deformation stress of ferrites,short and thin cementites with a width of about 20-50 nm and discontinuous length were formed. Shorter and thinner cementites were developed into ultra-fine pieces under the action of high density dislocation and strains. At the top surface,some cementites were decomposed under severe plastic deformation. Experimental evidences and analysis indicate that surface nanocrystallization of 45 steel results from dislocation activities,high strains and high strain rate are necessary for the formation of nanocrystallites.