We present experimental data and computational analysis of the formation of GaN nanowires on graphene virtual substrates. We show that GaN nanowires on graphene exhibit nitrogen polarity. We employ the DFT-based computational analysis to demonstrate that among different possible configurations of Ga and N atoms only the N-polar one is stable. We suggest that polarity discrimination occurs due to the dipole interaction between the GaN nanocrystal and π-orbitals of the graphene sheet.