Nanocrystalline chromium nitride and ternary chromium aluminium nitride thin films were deposited by reactive magnetron sputtering of Cr and Al targets in argon/nitrogen atmosphere varying the sputtering power and gas composition. The coatings were characterized in terms of crystal phase, chemical composition, microstructure, and mechanical properties by x-ray diffraction, x-ray photoelectron spectroscopy, including x-ray-induced Auger electron spectroscopy, transmission electron microscopy, selected-area electron diffraction, electron energy-loss spectroscopy, cross-sectional scanning electron microscopy, and ultramicrohardness tester. The incorporation of Al in the composition of the films produces an increase in the mechanical properties (hardness and reduced Young’s modulus) and an increased thermal resistance against oxidation in comparison to the pure CrN composition. The hardness behavior was attributed mainly to a reduction of the CrN crystallite size according to a Hall–Petch relationship. The oxidation resistance was evaluated after annealing both types of coatings in air up to 800°C. The oxygen content and the crystallite size appear almost unaltered in the CrAlN in contrast to the pure CrN films where the oxidation and grain growth is very noticeable at 800°C. This improvement in thermal stability in air is explained by the formation of a nanocomposite structure of small CrN crystals embedded in an amorphous aluminum oxide or oxinitride matrix that prevents the CrN phase from crystal growth and further oxidation.