Hydrogen is a long-term clean energy carrier that enables completely carbon-free energy production. However, practical implementation of hydrogen fuel technologies is restricted because of lack of safe and high-performing storage materials. Here, we report Mg nanocrystals encapsulated by narrow, bottom-up synthesized graphene nanoribbons (GNRs) as environmentally stable and high-capacity hydrogen storage materials. As an encapsulation medium, GNRs offer similar functionalities as reduced graphene oxide to protect the encapsulated Mg nanocrystals from extensive oxidation, while allowing penetrations of hydrogen. In addition, the GNRs can be edge functionalized to tune the (de-)hydrogenation kinetics, in particular for the processes occurred at the GNR-Mg interfaces. In this work, four different types of edge-functional groups were introduced into GNRs with the goal of comparing their cycling performances because of edge fimctionalization. On the basis of detailed kinetic analysis coupled with first principles calculations, we propose that edge-functional groups can contribute to the reduction of kinetic barriers for surface hydrogen reactions at the interface with the GNR by stabilizing surface defects. Furthermore, the GNR-Mg composite exhibited higher hydrogen storage capacity (7.1 wt % of hydrogen based on the total composite) compared with the current literature while demonstrating long-term air stability. This work suggests that the rational design of edge-functional groups in graphene derivatives can provide a general and novel paradigm for simultaneous encapsulation and hydrogen storage catalysis in simple metal or complex metal nanocrystals.