Hf and Zr nitrides are promising compounds for many technologically important areas, including high-temperature structural applications, quantum computing, and solar and optical applications. This article reports on a comprehensive first-principles statistical mechanics study of phase stability in the Hf-N and Zr-N binary systems. A high solubility of nitrogen in the hcp forms of Hf and Zr is predicted. The rocksalt forms of HfN and ZrN can also tolerate a high degree of off-stoichiometry through the introduction of nitrogen and metal vacancies. The Hf-N binary favors a family of stacking faulted parent crystal structures at intermediate nitrogen concentrations that host a unique form of short-range order among nitrogen interstitials and vacancies. These phases can accommodate some degree of configurational entropy and remain ordered to temperatures as high as 1200 K.