Nanoencapsulation using graphene derivatives enables the facile fabrication of two-dimensional (2D) nanocomposites with unique microstructures and has been generally applied to many fields of energy materials. Particularly, metal hydrides such as MgH2 encapsulated by graphene derivatives have emerged as a promising hybrid material for overcoming the disadvantageous properties of Mg-based hydrogen storage. Although the behavior of the graphene–Mg nanoencapsulation interface has been studied for many composite materials, the direct modification of graphene with nonmetal foreign elements for changing the interfacial behavior has been limitedly reported. In this regard, using B-doped graphene and N-doped graphene as nanoencapsulation media for tuning the interfacial behavior of graphene derivative–Mg nanoparticles, we present altered hydrogen storage kinetics of heteroatom-doped (B and N) graphene–Mg composites. The effect of heteroatom doping is studied in terms of bonding configurations and heteroatom doping concentrations. The enhancement in hydrogen uptake was observed for all of the heteroatom-doped graphene–Mg nanocomposites. On the other hand, a few samples exhibit significantly low activation energy at the early stage of desorption, which can be related to the facilitated nucleus formation. Density functional theory calculation indicates that B-doping and N-doping accelerate hydrogen absorption kinetics in different ways, aiding charge transfer and inducing surface deformation of Mg nanoparticles, respectively. Their effects can be augmented in the presence of structural defects on graphene, such as vacancies, pores, or graphene edges. These results demonstrate that hydrogen storage kinetics of Mg-based systems can be altered by utilizing heteroatom-doped graphene oxide derivatives as 2D nanoencapsulation media, suggesting that the addition of a nonmetal doping element can also be applied to Mg-based hydrogen storage by modifying the nanoencapsulation interface without forming Mg alloy phases.