The adsorption of hydrogen molecules on small iron clusters (Fen, n = 1–6) decorated on the surfaces of heptazine-based graphitic carbon nitride nanosheet/ graphene (hg‒C3N4‒NS/G) nanocomposites was investigated on the DFT level using PBE-D3 method for hydrogen storage applications. The results indicate that hydrogen adsorption occurs via physisorption, with adsorption energies ranging from −0.10 to −0.50 eV. Dissociative chemisorption is observed only for the first H2 molecule on larger clusters (Fen‒hg‒C3N4‒NS/G, n = 3‒6), exhibiting stronger binding energies of −1.11 to −1.75 eV, whereas subsequent hydrogen molecules adsorb through physisorption. According to the U.S. Department of Energy (DOE) criteria, the adsorption energy of H2 on Fe2‒hg‒C3N4‒NS/G falls within the optimal range for reversible hydrogen storage, indicating that Fe2‒hg‒C3N4‒NS/G structure is a promising candidate for efficient hydrogen storage materials.