Nanostructured surface layer was synthesized on 316L stainless steel by means of high-speed rotation wire-brushing deformation (HRWD). The refined microstructure features were systematically characterized by optical microscopy (OM), X-ray diffraction (XRD) analysis, and scanning electron microscopy (SEM) observations. Furthermore, the microhardness was examined by microhardness tester. After HRWD treatment, obvious grain refinement was observed and a nanocrystalline surface layer was formed on 316L stainless steel. It was found that a gradient microstructure with grain size from nanoscale to microscale was obtained along the depth of its surface layer. The thickness of the nanocrystalline surface layer varies from a few to about 20μm depending upon the treatment duration and compressive stress. The microhardness of nanostructured surface layer was enhanced significantly, and along the depth from the top surface, the microhardness in the surface gradually decreased to that of the matrix. Besides, the grain refinement mechanism and behaviors were discussed.