We study three structurally different states of nanocrystalline 316 steel and show that the state, where boundaries containing excess concentration of alloying elements are combined with mobile dislocations in grain interiors, allows maintaining extraordinarily high strength and remarkably enhanced plasticity. Underlying mechanisms featuring interaction between the segregations and mobile dislocations are discussed.