Abstract The influence of grain boundary segregation on the strength of a nanostructured austenitic stainless steel was investigated. The steel was nanostructured by severe plastic deformation at two different temperatures to form ultrafine-grained states different by microstructure parameters. It is shown that despite the difference in grain size both nanostructured steels demonstrated the same level of strength. For the first time it is directly observed that severe plastic deformation at elevated temperature leads to formation of Mo–Cr–Si rich grain boundary segregations in the steel. Considering different contributions to the material strengthening, we demonstrate that grain boundary segregations can lead to significant enhancement of the yield stress.