Recent studies demonstrated that the processing of metallic alloys by severe plastic deformation (SPD) can result in not only strong grain refinement but also leads to the formation of grain boundaries (GBs) with different structures, including GB segregations and precipitations. These nanostructural features of SPD-processed alloys produce considerable influence on their mechanical properties. The paper presents experimental data demonstrating a superstrength and positive slope of the HallPetch relation when passing from micro- to nanostructured state in a number of metallic materials subjected to severe plastic deformation. The nature of the superior strength is associated with new strengthening mechanisms and the difficulty of generation of dislocations from grain boundaries with segregations. This new approach is used for achieving the enhanced strength in several commercial Al and Ti alloys as well as steels subjected to SPD processing. © 2013 The Japan Institute of Metals and Materials.