A nanostructured surface layer was formed on an AISI 304 stainless steel with low stacking-fault energy by means of the surface mechanical attrition treatment (SMAT). The microstructure of the surface layer of the SMATed sample was characterized by using X-ray diffraction (XRD), scanning electron microscopy (SEM) and transmission electron microscopy (TEM), and cross-sectional TEM observation was performed to reveal the deformation-driven grain refinement mechanism for the f.c.c. materials with very low stacking-fault energy during SMAT. The grain refinement process in the surface layer involves formation of planar dislocation arrays and twins in deformed grains, twin–twin intersections leading to grain subdivision and a martensite transformation as well, and formation of randomly orientated refined crystallites. The formation of nanocrystallites in the top surface layer was ascribed to the much large strain and strain rate, as well as the multidirectional repetitive loading.