Interest in hydrogen fuel is growing for automotive applications; however, safe, dense, solid-state hydrogen storage remains a formidable scientific challenge. Metal hydrides offer ample storage capacity and do not require cryogens or exceedingly high pressures for operation. However, hydrides have largely been abandoned because of oxidative instability and sluggish kinetics. We report a new, environmentally stable hydrogen storage material constructed of Mg nanocrystals encapsulated by atomically thin and gas-selective reduced graphene oxide (rGO) sheets. This material, protected from oxygen and moisture by the rGO layers, exhibits exceptionally dense hydrogen storage (6.5 wt% and 0.105 kg H-2 per litre in the total composite). As rGO is atomically thin, this approach minimizes inactive mass in the composite, while also providing a kinetic enhancement to hydrogen sorption performance. These multilaminates of rGO-Mg are able to deliver exceptionally dense hydrogen storage and provide a material platform for harnessing the attributes of sensitive nanomaterials in demanding environments.