Increasing the yield stress of twinning-induced plasticity (TWIP) steels is a demanding task for modern materials science. This aim can be achieved by microstructure refinement induced by heavy straining. We feature the microstructural evolution and mechanical performance of a high-manganese TWIP steel subjected to deformation treatment by different combinations of equal channel angular pressing (ECAP) and rolling at different temperatures. The effect of microstructure on the tensile properties of the steel subjected to the multi-pass ECAP process and to subsequent rolling is reported as well. We show that the combined deformation procedure allows us to further increase the strength of the processed workpieces due to a gradual transition from a banded structure to a heterogeneous hierarchical microstructure consisting of fragments, dislocation configurations and nano-and micro-twins colonies. Rolling of multi-pass ECAP specimens at 375^◦C allowed us to achieve an extraordinary strength, the highest among all the investigated cases, while the best trade-off between yield strength and elongation to failure was reached using multi-pass ECAP followed by rolling at 500^◦C. This study shows a great potential of using combined deformation techniques to enhance the mechanical performance of TWIP steels.