Optical properties of GaN nanowires (NWs) grown on chemical vapor deposited-graphene transferred on an amorphous support are reported. The growth temperature was optimized to achieve a high NW density with a perfect selectivity with respect to a SiO2 surface. The growth temperature window was found to be rather narrow (815°C ± 5°C). Steady-state and time-resolved photoluminescence from GaN NWs grown on graphene was compared with the results for GaN NWs grown on conventional substrates within the same molecular beam epitaxy reactor showing a comparable optical quality for different substrates. Growth at temperatures above 820 °C led to a strong NW density reduction accompanied with a diameter narrowing. This morphology change leads to a spectral blueshift of the donor-bound exciton emission line due to either surface stress or dielectric confinement. Graphene multi-layered micro-domains were explored as a way to arrange GaN NWs in a hollow hexagonal pattern. The NWs grown on these domains show a luminescence spectral linewidth as low as 0.28 meV (close to the set-up resolution limit).