The theory of the effects of substitutions on the phase stabilities of Ti1-xAlxN was discussed. The substitution that increased the thermal stability of the NaCl structure of Ti1-xAlxN at high Al content was elaborated. Some possible avenues for such stabilization were presented and the substitution with nonmetal C and Si, and metal V, Cr and Mn was found to be most promising.