Enhancement in the strength of austenitic steels with a small content of carbon can be achieved by a limited number of methods, among which is ultrafine-grained (UFG) structure formation. This method is especially efficient with the use of severe plastic deformation (SPD) processing, which significantly increases the contribution of grain-boundary strengthening, and also involves a combination of the other strengthening factors (work hardening, twins, etc.). In this paper, we demonstrate that the use of SPD processing combined with conventional methods of deformation treatment of metals, such as rolling, may lead to additional strengthening of UFG steel. In the presented paper we analyze the microstructure and mechanical properties of the Cr–Ni stainless austenitic steel after a combined deformation. We report on substantial increases in the strength properties of this steel, resulting from a consecutive application of SPD processing via equal-channel angular pressing and rolling at a temperature of 400 °C. This combined loading yields a strength more than 1.5 times higher than those produced by either of these two techniques used separately.