This study reports the synthesis and characterization of ternary Cr-Al-O and quaternary Cr-Al-O-N coatings deposited by cathodic arc physical vapour deposition, for various nitrogen and oxygen mass flow ratios during the growth process. The composition, microstructure, indentation hardness and modulus of the films have been characterized by scanning electron microscopy, electron probe micro-analysis, X-ray diffraction, and nanoindentation techniques. The evolution of the microstructure and mechanical properties of the coatings after ambient air annealing from 800 °C up to 1100 °C have been investigated. As the oxygen to nitrogen mass flow increases, the as-deposited coatings exhibit lower hardness, higher roughness, lower crystallinity and a more marked columnar structure. At oxygen to nitrogen mass flow ratios bigger than 10/90, the coatings exhibit a stoichiometry of the type (CrAl)2+εO3−ε. Only the coatings with an oxygen to nitrogen mass flow ratio smaller than 10/90 retained nitrogen in their compositions. In all cases, the coatings developed a cubic fcc lattice structure. After annealing at 1100 °C the resulting microstructure showed a clear dependency upon the initial composition of the films. The evolution of the microstructure during the high temperature tests, as well as the analysis of the nanoindentation hardness, composition and thickness also provided valuable information about the combined effects of the thermal stability and the oxidation of the deposited coatings.