The interaction between C3N4 and three kinds of complex hydrides, LiAlH4, LiBH4, and NaAlH4, was investigated through density functional theory (DFT) computations. The adsorption of LiAlH4, LiBH4, and NaAlH4 is much stronger on C3N4 than other traditional carbon materials, such as graphene, carbon nanotubes, and fullerenes. Such strong interaction causes the electron redistribution in complex hydrides, and destabilizes Al/B–H bonds indirectly, thereby reducing the hydrogen removal energy. Moreover, C3N4 provides a very suitable adsorption site for AlHx/BHx (x = 3, 2, 1) units by the bond formation between Al/B and N atoms after losing H atoms. For the first step of dehydrogenation, due to the presence of C3N4, the H-removal energies decrease significantly. In addition, the adsorption energy of H2 molecule on C3N4 is so low that C3N4 would not capture the released H2 from complex hydrides. Therefore, C3N4 is a potential catalyst for H2 release from complex hydrides.