Epitaxial growth of GaN nanowires on graphene is demonstrated using molecular beam epitaxy without any catalyst or intermediate layer. Growth is highly selective with respect to silica on which the graphene flakes, grown by chemical vapor deposition, are transferred. The nanowires grow vertically along their c-axis and we observe a unique epitaxial relationship with the ⟨21̅1̅0⟩ directions of the wurtzite GaN lattice parallel to the directions of the carbon zigzag chains. Remarkably, the nanowire density and height decrease with increasing number of graphene layers underneath. We attribute this effect to strain and we propose a model for the nanowire density variation. The GaN nanowires are defect-free and they present good optical properties. This demonstrates that graphene layers transferred on amorphous carrier substrates is a promising alternative to bulk crystalline substrates for the epitaxial growth of high quality GaN nanostructures.