In this work we shed light on the early stage of the chemical vapor deposition of graphene on Ge(001) surfaces. By a combined use of microRaman and x-ray photoelectron spectroscopies, and scanning tunneling microscopy and spectroscopy, we were able to individuate a carbon precursor phase to graphene nucleation which coexists with small graphene domains. This precursor phase is made of C aggregates with different size, shape and local ordering which are not fully sp2 hybridized. In some atomic size regions these aggregates show a linear arrangement of atoms as well as the first signature of the hexagonal structure of graphene. The carbon precursor phase evolves in graphene domains through an ordering process, associated to a re-arrangement of the Ge surface morphology. This surface structuring represents the embryo stage of the hills-and-valleys faceting featured by the Ge(001) surface for longer deposition times, when the graphene domains coalesce to form a single layer graphene film.