In this paper, four kinds of hard coatings, TiN, CrN, TiAlN and CrAlN (with Al/Ti or Al/Cr atomic ratio around 1:1), were deposited on stainless steel substrates by a lateral rotating cathode arc technique. The as-deposited coatings were annealed in ambient atmosphere at different temperatures (500–1000 °C) for 1 h. The evolution of chemical composition, microstructure, and microhardness of these coatings after annealing at different temperatures was systematically analyzed by energy dispersive X-ray spectroscopy (EDX), X-ray diffraction (XRD) and nanoindentation experiments. The oxidation behaviour and its influence on overall hardness of these four coatings were compared. It was found that the ternary TiAlN and CrAlN coatings have better oxidation resistance than their binary counterparts, TiN and CrN coatings. The Cr-based coatings (CrN and CrAlN) exhibited evidently better oxidation resistance than the Ti-based coatings (TiN and TiAlN). TiN coating started to oxidize at 500 °C. After annealing at 700 °C no N could be detected by EDX, indicating that the coating was almost fully oxidized. After annealed at 800 °C, the coating completely delaminated from the substrate. TiAlN started to oxidize at 600 °C. It was nearly fully oxidized (with little residual nitrogen detected in the coating by EDX) and partially delaminated at 1000 °C. Both CrN and CrAlN started to oxidize at 700 °C. CrN was almost fully oxidized (with little residual nitrogen detected in the coating by EDX) and partially delaminated at 900 °C. The oxidation rate of the CrAlN coating is quite slow. After annealing at 1000 °C, only about 19 at.% oxygen was detected and the coating showed no delamination. The Ti-based (TiN and TiAlN) coatings were not able to retain their hardness at higher temperatures (≥ 700 °C). On the other hand, the hardness of CrAlN was stable at a high level between 33 and 35 GPa up to an annealing temperature of 800 °C and still kept at a comparative high value of 18.7 GPa even after annealed at 1000 °C, indicating a very promising applicability of this coating for high speed dry machining and other applications under high temperature environments.