The strengthening mechanism of the metallic material is related to the hindrance of the dislocation motion, and it is possible to achieve superior strength by maximizing these obstacles. In this study, the multiple strengthening mechanism-based nanostructured steel with high density of defects was fabricated using high-pressure torsion at room and elevated temperatures. By combining multiple strengthening mechanisms, we enhanced the strength of Fe-15 Mn-0.6C-1.5 Al steel to 2.6 GPa. We have found that solute segregation at grain boundaries achieves nanograined and nanotwinned structures with higher strength than the segregation-free counterparts. The importance of the use of multiple deformation mechanism suggests the development of a wide range of strong nanotwinned and nanostructured materials via severe plastic deformation process.