A gradient nanostructured layer (GNsL) was generated on the two sides of bulk sample in 304L stainless steel by means of the surface mechanical attrition treatment. The microstructure of the GNsL was characterized via TEM observation. The prominent microstructural features involve the intersection of multi-system twin operation, subdividing the original grains into blocks, a martensite transformation mainly occurring at the interface of the twins as well, and the randomly orientated nanocrystallites at the top of surface. After annealing at 750°C for 10 min, recovery had occurred and the dislocation density was much reduced. The vast majority of the grains at the top surface were in the nanocrystalline/ultrafine range, with some recrystallization regions. The uniaxial tensile tests were performed to obtain the mechanical property of bulk samples with GNsL. The yield strength was about 2 times higher than that of the coarse-grained counterpart, but with a decrease in uniform elongation and elongation to failure as well. The relationship between the microstructure and mechanical property was discussed in detail.