Complex hydrides are mixed ionic–covalent compounds that can serve as reversible H2 storage media only when they are catalyzed by a transition metal such as Ti. As the prime example, the phenomenology of Ti-catalyzed sodium alanate (NaAlH4) is reviewed from a historical perspective. Dehydriding yields a theoretical 5.6 wt% H2 during two-step decomposition, NaAlH4 → Na3AlH6 → NaH + Al, although 100% recovery of that H2 is not currently possible. H2 can be discharged and recharged at practical rates at 125°C. More work is needed on the alanates, in particular, as well as the identification and optimization of the catalytic mechanism and a broad extension of the concept to other than Na-based alanates. The possibility of an even further extension of the concept to other complex hydrides (e.g., the borohydrides and transition-metal complexes) is discussed.