The metals and alloys subjected to severe plastic deformation (SPD) can possess not only ultrafine-grained structure but also specific nanostructural features, such as non-equilibrium grain boundaries, nanotwins, grain boundary segregations and nano particles. The present work considers the role some 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.