We investigate the evolution of CVD-grown graphene/Ge(001) as a function of the deposition temperature in close proximity to the Ge melting point, highlighting an abrupt change of the graphene’s quality, morphology, electronic properties and growth mode at 930 °C. We attribute this discontinuity to the incomplete surface melting of the Ge substrate and show how incomplete melting explains a variety of diverse and long-debated peculiar features of the graphene/Ge(001), including the characteristic nanostructuring of the Ge substrate induced by graphene overgrowth. We find that the quasi-liquid Ge layer formed close to 930 °C is fundamental to obtain high-quality graphene, while a temperature decrease of 10 degrees already results in a wrinkled and defective graphene film.