The nanostructured surface layers were fabricated on a hardened and tempered chrome-silicon alloy steel and a normalized medium carbon steel by mean of Supersonic Fine Particles Bombarding (SFPB). The microstructure features in the treated surface layer were characterized using X-ray diffraction (XRD), scanning electron microscopy (SEM) and transmission electron microscopy (TEM) observations. Experimental results show the nanostructured surface layer is fabricated on both samples after SFPB treatment. The microstructure of the top surface is characterized by uniformly distributed nano-scale grains with equiaxed shape and random crystallographic orientations. The mean size of equiaxed nanocrystallites on the top surface layer is approximately 15-20nm for the SFPB treated medium carbon steel and Chrome-silicon alloy steel. During severe deformation the grain refinement in ferrite and cementite phases is observed, the cementite phases are exposed to breaking and dissolution due to mechanical alloying resulting in the formation of a supersaturated solid solution of carbon in α-Fe matrix. In the ferrite phase, the grains are refined by the process of dislocation actives and forming cell structures separated by dense dislocation walls (DDWs), as well as evolution of dislocation to subboundaries and grain boundaries.