We investigate structural and electronic properties of the graphene-like gallium nitride (GaN) monolayer deposited on a MoSe2 monolayer by using density functional theory with the inclusion of the nonlocal van der Waals correction. The GaN is bound weakly to the MoSe2 monolayer with adsorption energy of 49 meV/atom. We find that the heterobilayer is energetically favorable with the interlayer distance of 3.302 A indicating van der Waals (vdW) type interaction and the most stable stacking configuration is verified with different deposition sequences. The heterostructure of GaN/MoSe2 is found to be indirect band gap semiconductor with gap value of 1.371 eV. Our results demonstrate the potential design of new two-dimensional nanoelectronic devices based on the vdW heterostructure.