The growth of GaN on graphene by molecular beam epitaxy was investigated. The most stable epitaxial relationship, i.e. [00.1]-oriented grains, is obtained at high temperature and N-rich conditions, which match those for nanowire growth. Alternatively, at moderate temperature and Ga-rich conditions, several metastable orientations are observed at the nucleation stage, which evolve preferentially towards [00.1]-oriented grains. The dependence of the nucleation regime on growth conditions was assigned to Ga adatom kinetics. This statement is consistent with the calculated graphene/GaN in-plane lattice coincidence and supported by a combination of transmission electron microscopy, x-ray diffraction, photoluminescence, and Raman spectroscopy experiments.