Strain modulation is crucial for heteroepitaxy such as GaN on foreign substrates. Here, the epitaxy of strain-relaxed GaN films on graphene/SiC substrates by metal-organic chemical vapor deposition is demonstrated. Graphene was directly prepared on SiC substrates by thermal decomposition. Its pre-treatment with nitrogen-plasma can introduce C-N dangling bonds, which provides nucleation sites for subsequent epitaxial growth. The scanning transmission electron microscopy measurements confirm that part of graphene surface was etched by nitrogen-plasma. We study the growth behavior on different areas of graphene surface after pre-treatment, and propose a growth model to explain the epitaxial growth mechanism of GaN films on graphene. Significantly, graphene is found to be effective to reduce the biaxial stress in GaN films and the strain relaxation improves indium-atom incorporation in InGaN/GaN multiple quantum wells (MQWs) active region, which results in the obvious red-shift of light-emitting wavelength of InGaN/GaN MQWs. This work opens up a new way for the fabrication of GaN-based long wavelength light-emitting diodes.