The transition from (inter)metallic to substoichiometric regime and therewith associated microstructural modifications within arc evaporated Al-Cr-based oxide coatings was investigated. The dense columnar intermetallic structure is subject to grain refinement when increasing the O2 flow rate during the deposition. Cr-rich, O-depleted crystalline domains (initially short columnar, then equiaxed globular) and an amorphous Al- and O-enriched boundary phase develops—with increasing volume fraction for higher O2 flow rates. Such nanocomposites, originating from preferred oxide phase formation of Aluminium, can effectively be adjusted by the amount of oxygen and the nominal cathode composition used during synthesis.