The phase stability and mechanical properties of wurtzite (w)-Zr0.25Al0.75N/cubic (c)-TiN and w-Zr0.25Al0.75N/c-ZrN multilayers grown by arc evaporation are studied. Coherent interfaces with an orientation relation of c-TiN (111)[1-10]||w-ZrAlN (0001)[11-20] form between ZrAlN and TiN sublayers during growth of the w-ZrAlN/c-TiN multilayer. During annealing at 1100 °C a c-Ti(Zr)N phase forms at interfaces between ZrAlN and TiN, which reduces the lattice mismatch so that the coherency and the compressive strain are partially retained, resulting in an increased hardness (32 GPa) after annealing. For the w-ZrAlN/c-ZrN multilayer, there is no coherency between sublayers leading to strain relaxation during annealing causing the hardness to drop. The retained coherency between layers and the compressive strain in the w-ZrAlN/c-TiN multilayer results in superior fracture toughness compared to the w-ZrAlN/c-ZrN multilayer as revealed by cross-sectional investigations of damage events under scratch and indentation tests.