Exploratory synthesis in novel 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 7 new Zn- and Mg-based ternary nitrides. By extracting the mixed metallicity, ionicity, and covalency of solid-state bonding from the 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.