Hydrogen is a promising alternative energy carrier that can potentially facilitate the transition from fossil fuels to sources of clean energy because of its prominent advantages such as high energy density (142 MJ kg(-1); ref. 1), great variety of potential sources (for example water, biomass, organic matter), light weight, and low environmental impact (water is the sole combustion product). However, there remains a challenge to produce a material capable of simultaneously optimizing two conflicting criteria--absorbing hydrogen strongly enough to form a stable thermodynamic state, but weakly enough to release it on-demand with a small temperature rise. Many materials under development, including metal-organic frameworks, nanoporous polymers, and other carbon-based materials, physisorb only a small amount of hydrogen (typically 1-2 wt%) at room temperature. Metal hydrides were traditionally thought to be unsuitable materials because of their high bond formation enthalpies (for example MgH(2) has a ΔHf~75 kJ mol(-1)), thus requiring unacceptably high release temperatures resulting in low energy efficiency. However, recent theoretical calculations and metal-catalysed thin-film studies have shown that microstructuring of these materials can enhance the kinetics by decreasing diffusion path lengths for hydrogen and decreasing the required thickness of the poorly permeable hydride layer that forms during absorption. Here, we report the synthesis of an air-stable composite material that consists of metallic Mg nanocrystals (NCs) in a gas-barrier polymer matrix that enables both the storage of a high density of hydrogen (up to 6 wt% of Mg, 4 wt% for the composite) and rapid kinetics (loading in <30 min at 200 °C). Moreover, nanostructuring of the Mg provides rapid storage kinetics without using expensive heavy-metal catalysts.