The metals and alloys subjected to severe plastic deformation can possess not only ultrafine-grained (UFG) structure but also specific nanostructural features, such as nonequilibrium grain boundaries, nanotwins, grain boundary segregations and nano particles. The authors consider in the present work the role of these features in exhibition of high strength of nanostructured metals and alloys. In particular, it is demonstrated that the presence of grain boundary segregations and non-equilibrium boundaries can result in yield stress values that considerably exceed those predicted from the Hall-Petch relation for the given materials.