The deformation microstructures and their effects on mechanical properties of austeniticstainless steels processed by cold rolling at ambient temperature to various total strains were studied. The cold working was accompanied by the development of strain-induced martensitic transformation because of meta-stable austenite at room temperature. The strain-induced martensitic transformation and deformation twinning promoted the grain refinement during cold rolling, leading to nanocrystalline structures consisting of a mixture of austenite and martensite grains with their transverse grain sizes of 50-150 nm containing high dislocation densities. The rolled samples experienced substantial strengthening resulted from high density of strain induced grain/phase boundaries and dislocations. The yield strength of austenitic stainless steels could be increased to 2000 MPa after rolling to total strains of about 4. The martensite and austenite provided almost the same contribution to overall yield strength. The dislocation strengthening was much higher than the grain boundary strengthening at small to moderate strains of about 2, whereas the latter gradually increased approaching the level of dislocation strengthening with increasing the strain.