For hydrogen to be successfully used as an energy carrier in a new renewable energy driven economy, more efficient hydrogen storage technologies have to be found. Solid-state hydrogen storage in complex metal hydrides, such as sodium alanate (NaAlH4), is a well-researched candidate for this application. A series of NaAlH4/mesoporous carbon black composites, with high NaAlH4 content (50–90 wt%), prepared via ball milling have demonstrated significantly lower dehydrogenation temperatures with intense dehydrogenation starting at ∼373 K compared to bulk alanate's ≥ 456 K. Dehydrogenation/hydrogenation cycling experiments have demonstrated partial hydrogenation at 6 MPa H2 and 423 K. The cycling experiments combined with temperature-programmed dehydrogenation and powder X-ray diffraction have given insight into the fundamental processes driving the H2 release and uptake in the NaAlH4/carbon composites. It is established that most of the hydrogenation behavior can be attributed to the Na3AlH6 ↔ NaH transition.