We present first-principles density functional calculations of the electronic structure, magnetism, and structural stability of 378 XYZ half-Heusler compounds (with X= Cr, Mn, Fe, Co, Ni, Ru, Rh, Y= Ti, V, Cr, Mn, Fe, Ni, Z= Al, Ga, In, Si, Ge, Sn, P, As, Sb). We find that a “Slater-Pauling density of states” with a gap or pseudogap at three states per atom below the gap in at least one spin channel is a common feature in half-Heusler compounds. We find that the presence of such a gap at the Fermi energy in one or both spin channels contributes greatly to the stability of a half-Heusler compound. We calculate the formation energy of each compound and systematically investigate its stability against all other phases in the Open Quantum Materials Database (OQMD). We represent the thermodynamic phase stability of each compound as its distance from the convex hull of stable phases in the respective chemical space and show that the hull distance of a compound is a good measure of the likelihood of its experimental synthesis. We identify 26 18-electron semiconductors, 45 half-metals, and 34 near half-metals with negative formation energy, that follow the Slater-Pauling rule of three electrons per atom. Our calculations predict new thermodynamically stable semiconducting phases NiScAs, RhTiP, and RuVAs, which merit further experimental exploration. Further, two interesting zero-moment half-metals, CrMnAs and MnCrAs, are calculated to have negative formation energy. In addition, our calculations predict a number of new, hitherto unreported, semiconducting (e.g., CoVGe, FeVAs), half-metallic (e.g., RhVSb), near half-metallic (e.g., CoFeSb, CoVP) half-Heusler compounds to lie close to the respective convex hull of stable phases, and thus may be experimentally realized under suitable synthesis conditions, resulting in potential candidates for various spintronics applications.