A model coupling first principles and thermodynamics was developed to describe the thermal stability of a nanograin structure in solid solution alloys. The thermodynamic functions of solute segregation and conditions for thermal stabilization were demonstrated for both strongly and weakly solute-segregating systems. The dependence of segregation behavior on the grain size, solute concentration and temperature was quantified, where the parameters to control destabilization of the nanograin structure at a given temperature were predicted. For the first time it was found that there exists a transformation from the single-extreme to dual-extreme rule of the total Gibbs free energies of the solid solution systems with the decrease of solute concentration or increase of temperature. The model calculations were confirmed quantitatively by the experimental results, and a nanocrystalline W-10 at%Sc solid solution with a highly stable grain structure in a broad range from room temperature to 1600 K was prepared. The universal mechanism disclosed in this study will facilitate the design of nanocrystalline alloys with high thermal stability through matching of the doping element and the initial grain size.