The formation of nanocrystalline structures and mechanical properties were studied in a nitrogen-bearing 304-type stainless steel subjected to severe plastic deformation (SPD). The steel samples were processed at ambient temperature using three different methods, i.e., caliber rolling, multidirectional forging and high pressure torsion. All these techniques resulted in pronounced grain refinement. The microstructures consisting of austenite/ferrite crystallites with transverse dimensions of 50 and 30 nm evolved in the rolled and forged samples, respectively. The austenitefractions comprised approximately 0.4. In contrast, the microstructure consisted mainly of austenite with an average grain size of about 25 nm evolved after high pressure torsion. All samples of the stainless steel subjected to severe plastic deformation demonstrated significant strengthening. The ultimate tensile strengths of 2065 MPa and 1950 MPa, were obtained after rolling and high pressure torsion, respectively. The ultimate tensile strength of samples subjected to multidirectional forging was 1540 MPa.