Here, we report the fabrication of a graphene-wrapped nanostructured reactive hydride composite, i.e., 2LiBH4-MgH2, made by adopting graphene-supported MgH2 nanoparticles (NPs) as the nanoreactor and heterogeneous nucleation sites. The porous structure, uniform distribution of MgH2 NPs, and the steric confinement by flexible graphene induced a homogeneous distribution of 2LiBH4-MgH2 nanocomposite on graphene with extremely high loading capacity (80 wt%) and energy density. The well-defined structural features, including even distribution, uniform particle size, excellent thermal stability, and robust architecture endow this composite with significant improvements in its hydrogen storage performance. For instance, at a temperature as low as 350 °C, a reversible storage capacity of up to 8.9 wt% H2, without degradation after 25 complete cycles, was achieved for the 2LiBH4-MgH2 anchored on graphene. The design of this three-dimensional architecture can offer a new concept for obtaining high performance materials in the energy storage field.