In this paper, we report amorphous-carbon-supported TiB2 nanoparticles having sizes of 2–4 nm (nano-TiB2@C) as highly active catalysts for hydrogen storage in NaAlH4. Nano-TiB2@C was synthesized by a simple calcination at 550°C with Cp2TiCl2 and MgB2 (molar ratio of 1:1) as precursors. The addition of 7 wt% nano-TiB2@C reduced the onset dehydrogenation temperature of NaAlH4 by 100 to 75°C. A practically available hydrogen capacity of 5.04 wt% could be desorbed at 140°C within 60 min, and completely hydrogenated at 100°C within 25 min under a hydrogen pressure of 100 bar. Notably, the hydrogen capacity was almost unchanged after 20 cycles, which shows the stable cyclability, considerably higher than those of structures catalyzed by Ti halides or TiO2. The stable catalytic function was closely related to the in-situ-formed Ti–Al alloy, which considerably facilitated the dissociation and recombination of H–H and Al–H bondings.