A synergistic approach involving experiment and first-principles theory not only shows that carbon nanostructures can be used as catalysts for hydrogen uptake and release in complex metal hydrides such as sodium alanate, NaAlH(4), but also provides an unambiguous understanding of how the catalysts work. Here we show that the stability of NaAlH(4) originates with the charge transfer from Na to the AlH(4) moiety, resulting in an ionic bond between Na(+) and AlH(4)(-) and a covalent bond between Al and H. Interaction of NaAlH(4) with an electronegative substrate such as carbon fullerene or nanotube affects the ability of Na to donate its charge to AlH(4), consequently weakening the Al-H bond and causing hydrogen to desorb at lower temperatures as well as facilitating the absorption of H(2) to reverse the dehydrogenation reaction. In addition, based on our experimental observations and theoretical calculations it appears the curvature of the carbon nanostructure plays a role in the catalytic process. Ab initio molecular dynamics simulation further reveals the time evolution of the charge transfer process.