Ultra-fine-grained (UFG) metals and alloys have unique mechanical properties at room temperature. However, their grains grow rapidly even at low and mediate temperatures due to the high density of grain boundaries which largely increase their Gibbs free energy. Thus, improving the thermal stability of UFG metals and alloys should be critical to their processing and application at elevated temperatures. In this report, the thermal stability of UFG Ni alloys is studied by changing the type and content of such solutes as Fe, Cr and V. The thermal stability is theoretically predicted by the change in free energy due to solute segregation and by the normalized grain boundary free energy. The thermal stability is also experimentally examined by the change in microhardness after annealing. The experimental results agree well with the theoretical predictions. The thermal stability of UFG Ni is significantly improved by the grain boundary segregation of V and moderately improved by the grain boundary segregation of Cr and Fe. Furthermore, increasing the content of solute improves the thermal stability of UFG Ni(Cr) alloys. Our study should help design UFG Ni alloys with improved thermal stability for practical applications.