We report an ab-initio study of the preferred polarity for wurtzite GaN nanostructures on virtual graphene substrates. By means of the density functional theory analysis we show that N-polar nanostructures on graphene are energetically favorable in comparison to Ga-polar. These finding are in agreement with experimentally observed N-polarity of wurtzite GaN nanowires grown on graphene substrate. We believe that the revealed polarity preference is of importance for piezoelectric and optoelectronic device design.