With the perspective of using two-dimensional materials as growth substrates for semiconductors, we explore the nucleation of GaN nanostructures on graphene. Using plasma-assisted molecular beam epitaxy, we investigate what happens during the long incubation time which precedes the epitaxy of the first GaN islands. After 30 min of nitrogen plasma exposure with no deposition, we find that graphene is modified, and we identify C–N bonds. We measure and model the variation of the incubation time with the growth parameters. These data support the idea that graphene must be modified before GaN nucleation becomes possible. We then test the adhesion at the interface between graphene and the GaN nanostructures. Our studies converge on the conclusion that GaN nanostructures nucleate on graphene from pyridinic N atoms incorporated in the lattice, which are responsible for strong binding between the two materials.