With the aid of supercritical CO2, Fe-, Ni-, Pd-, and Au-nanoparticle-decorated nanostructured carbon materials (graphene, activated carbon, carbon black, and carbon nanotubes) are synthesized for catalyzing the dehydrogenation of LiAlH4. The effects of the metal nanoparticle size and distribution, and the type of carbon structure on the hydrogen release properties are investigated. The Fe/graphene nanocomposite, which consists of ∼2 nm Fe particles highly dispersed on graphene nanosheets, exhibits the highest catalytic performance. With this nanocomposite, the initial dehydrogenation temperature can be lowered (from ∼135 °C for pristine LiAlH4) to ∼40 °C without altering the reaction route (confirmed by in situ X-ray diffraction), and 4.5 wt% H2 can be released at 100 °C within 6 min, which is faster by more than 135-fold than the time required to release the same amount of H2 from pristine LiAlH4.