Nanostructure formation via surface-diffusion-mediated segregation of ZrN and AlN in Zr1−xAlxN films during high mobility growth conditions is investigated for 0 ≤ × ≤ 1. The large immiscibility combined with interfacial surface and strain energy balance resulted in a hard nanolabyrinthine lamellar structure with well-defined (semi) coherent c-ZrN and w-AlN domains of sub-nm to ~4 nm in 0.2 ≤ × ≤ 0.4 films, as controlled by atom mobility. For high AlN contents (x > 0.49) Al-rich ZrN domains attain wurtzite structure within fine equiaxed nanocomposite wurtzite lattice. Slow diffusion in wurtzite films points towards crystal structure dependent driving force for decomposition. The findings of unlikelihood of iso-structural decomposition in c-Zr1−xAlxN, and stability of w-Zr1−xAlxN (in large × films) is complemented with first principles calculations.