The work aims to investigate the mechanisms of grain refinement and plastic deformation of the surface nano-crystallization by conducting surface nano-treatment to ferrite/martensite (F/M) steels with different microstructures. Supersonic Fine Particles Bombarding (SFPB) technology was used to conduct nano-treatment to the dual phase steel after intercritical an-nealing (IA), intermediate quenching (IQ) and step quenching (SQ). SEM, OM and XRD were applied to study the surface mi-crostructure of experimental steel before and after SFPB. The surface microhardness was measured by Microhardness Tester and the tensile experiment was used to test the mechanical property. The martensites specimens after IA, IQ and SQ appeared island, fibrous, and massive shape after the heat treatment. The specimen after IQ had the smallest average grain size and the largest martensite volume fraction. After SFPB process, the gradient nanostructured surface (GNS) layer with certain thickness was fabricated on the dual phase steel and the average minimum grain size reached nanoscale and grew with increase of the in-depth distance to the surface. The surface microhardness of IA-GNS, IQ-GNS and SQ-GNS specimens was 285.9, 266.7 and 382.1HV, the tensile strength was 771.30, 820.02 and 663.81 MPa, and the elongation rate was 8.89%, 14.70% and 10.04%, respectively. Many dimples were found from the fracture surface of IQ-GNS specimen, while fewer dimples and clear cracks existed in SQ-GNS and IA-GNS specimens. The grain size can be refined to the nanoscale due to the segmentation of dislocation as a result of the improvement of the material strength when the severe plastic deformation occurs, and the IQ-GNS specimen can still keep the good toughness owing to the existence of the fibrous martensite microstructure.