Increasing the strength of low carbon austenitic steels, which are not hardened by quenching, is possible due to the formation of ultrafine-grained (UFG) structure during severe plastic deformation (SPD). However, the most notable hardening during SPD is observed at the initial stages of processing, after which the hardening rate decreases markedly. One of deformation parameters significantly affecting the structure is loading path. Using non-monotonic loading allows one to activate new glide systems resulting in an accelerated process of UFG structure formation and the resulting structures are characterized by high dislocation density and smaller grain sizes. In this work, non-monotonic loading by a combination of two methods, equal channel angular pressing (ECAP) and subsequent rolling with varying reduction rate, was used. It has been shown that the combination of SPD method (ECAP) and rolling leads to an additional increase in the microhardness of UFG austenitic steel. Additional hardening is associated with features of the microstructure formed under combined loading. The structure is characterized by a fine grain size and high density of dislocations compared with the structure after rolling or ECAP. It is shown that during deformation the microstructure changed from banded structure to a subrgrain-granular one. For the samples subjected to ECAP before rolling this process occurs at a less rolling strain. Furthermore, after the combined loading a noticeable volume fraction of twins in the microstructure was observed as compared to their rather small amount after ECAP. With a strain increase during rolling the rate of microhardness growth slows down.