Exploratory synthesis in new chemical spaces is the essence of solid-state chemistry. However, uncharted chemical spaces can be difficult to navigate, especially when materials synthesis is challenging. Nitrides represent one such space, where stringent synthesis constraints have limited the exploration of this important class of functional materials. Here, we employ a suite of computational materials discovery and informatics tools to construct a large stability map of the inorganic ternary metal nitrides. Our map clusters the ternary nitrides into chemical families with distinct stability and metastability, and highlights hundreds of promising new ternary nitride spaces for experimental investigation-from which we experimentally realized seven new Zn- and Mg-based ternary nitrides. By extracting the mixed metallicity, ionicity and covalency of solid-state bonding from the density functional theory (DFT)-computed electron density, we reveal the complex interplay between chemistry, composition and electronic structure in governing large-scale stability trends in ternary nitride materials.