Metal hydrides with enhanced thermodynamic stability with respect to the associated binary hydrides are useful for high temperature applications in which highly stable materials with low hydrogen overpressures are desired. Though several examples of complex transition metal hydrides (CTMHs) with such enhanced stability are known, little thermodynamic or phase stability information is available for this materials class. In this work, we use semiautomated thermodynamic and phase diagram calculations based on density functional theory (DFT) and grand canonical linear programming (GCLP) methods to screen 102 ternary and quaternary CTMHs and 26 ternary saline hydrides in a library of over 260 metals, intermetallics, binary, and higher hydrides to identify materials that release hydrogen at higher temperatures than the associated binary hydrides and at elevated temperatures, T > 1000 K, for 1 bar H-2 overpressure. For computational efficiency, we employ a tiered screening approach based first on solid phase ground state energies with temperature effects controlled via H-2 gas alone and second on the inclusion of phonon calculations that correct solid phase free energies for temperature-dependent vibrational contributions. We successfully identified 13 candidate CTMHs including Eu2RuH6, Yb2RuH6, Ca2RuH6, Ca2OsH6, Ba2RuH6, Ba3Ir2H12, Li4RH4, NaPd3H2, Cs2PtH4, K2PtH4, Cs3PtH5, Cs3PdH3, and Rb2PtH4. The most stable CTMHs tend to crystallize in the Sr2RuH6 cubic prototype structure and decompose to the pure elements and hydrogen rather than to intermetallic phases.