Aiming to design stable nanocrystalline (NC) materials, so far, it has been proposed to construct nanostructure stability maps in terms of thermodynamic parameters, while kinetic stabilization has seldom been considered, despite the synergy of thermodynamics and kinetics. Consequently, the thermodynamically stabilized NC materials may be easily subjected to grain growth at high temperatures due to the weakly kinetic stabilization. Starting from the thermo-kinetic synergy, a stabilization criterion is proposed as a function of intrinsic solute parameters (e.g. the activation energy for bulk diffusion and the segregation enthalpy), intrinsic solvent parameters (e.g. the intrinsic activation energy for GB migration and the GB energy) and processing parameters (e.g. the grain size, the temperature and the solute concentration). Using first-principles calculations for a series of combinations between fifty-one substitutional alloying atoms as solute atoms and Fe atom as fixed solvent atom, it is shown that the thermal stability neither simply increases with increasing the segregation enthalpy as expected by thermodynamic stabilization, nor monotonically increases with increasing the activation energy for bulk diffusion as described by kinetic stabilization. By combination of thermodynamic and kinetic contributions, the current stabilization criterion evaluates quantitatively the thermal stability, thus permitting convenient comparisons among NC materials involved by various combinations of the solute atoms, the solvent atoms, or the processing conditions. Validity of this thermo-kinetic stabilization criterion has been tested by current experiment results of Fe-Y alloy and previously published data of Fe-Ni, Fe-Cr, Fe-Zr and Fe-Ag alloys, etc., which opens a new window for designing NC materials with sufficiently high thermal stability and sufficiently small grain size.