State-of-the-art alloys for hard coating applications, such as TiAlN, are known to suffer from decreased hardness during heat treatment in excess of 900 °C due to the formation of detrimental wurtzite AlN phases. Recent research has shown that multicomponent alloying with additional transition metals (TMs) such as Cr can shift the onset of the phase transformations to higher temperatures, but a search for new alloys is generally time-consuming due to the large number of processes that influence material properties along with the large number of alloy compositions that have to be synthesized. To overcome this difficulty we carry out systematic first-principles calculations aimed at finding potential new multicomponent TM aluminum nitride alloys for advanced hard coating applications. We direct our search towards a specific property, the thermal stability of the coating. In particular, we concentrate on the thermodynamic stability of the cubic B1 TM–Al–N phase relative to the wurtzite phase, and choose the enthalpy difference between them as our search descriptor. We perform ab initio calculations for all TMs, considered as impurities in AlN, and identify the most promising candidates that may improve the thermal stability. We present arguments that these elements should be targeted in future in-depth studies, theoretical, as well as experimental.