Thermal stability of protective coatings is one of the performance-defining properties for advanced cutting and forming applications as well as for energy conversion. To investigate the effect of oxygen incorporation on the high-temperature behavior of (Ti,Al)N, metastable cubic (Ti,Al)N and (Ti,Al)(O _xN _{1- x}) coatings are synthesized using reactive arc evaporation. X-ray diffraction of (Ti,Al)N and (Ti,Al)(O _xN _{1- x}) coatings reveals that spinodal decomposition is initiated at approximately 800°C, while the subsequent formation of wurtzite solid solution is clearly delayed from 1000°C to 1300°C for (Ti,Al)(O _xN _{1- x}) compared to (Ti,Al)N. This thermal stability enhancement can be rationalized based on calculated vacancy formation energies in combination with spatially-resolved composition analysis and calorimetric data: Energy dispersive X-ray spectroscopy and atom probe tomography data indicate a lower O solubility in wurtzite solid solution compared to cubic (Ti,Al)(O,N). Hence, it is evident that for the growth of the wurtzite, AlN-rich phase in (Ti,Al)N, only mobility of Ti and Al is required, while for (Ti,Al)(O,N), in addition to mobile metal atoms, also non-metal mobility is required. Prerequisite for mobility on the non-metal sublattice is the formation of non-metal vacancies which require larger temperatures than for the metal sublattice due to significantly larger magnitudes of formation energies for the non-metal vacancies compared to the metal vacancies. This notion is consistent with calorimetry data which indicate that the combined energy necessary to form and grow the wurtzite phase is larger by a factor of approximately two in (Ti,Al)(O,N) than in (Ti,Al)N, causing the here reported thermal stability increase.