On the path to functional graphene electronics, suitable templates for chemical vapor deposition (CVD) growth of high-mobility graphene are of great interest. Among various substrates, hexagonal boron nitride (h-BN) has established itself as one of the most promising candidates. The nanomesh, a h-BN monolayer grown on the Rh(111) surface where the lattice mismatch of h-BN and rhodium leads to a characteristic corrugation of h-BN, offers an interesting graphene/h-BN interface, different from flat graphene/h-BN systems hitherto studied. In this report, we describe a two-step CVD process for graphene formation on h-BN/Rh(111) at millibar pressures and describe the influence of the surface texture on the CVD process. During a first exposure to the 3-pentanone precursor, carbon atoms are incorporated in the rhodium subsurface, which leads to decoupling of the h-BN layer from the Rh(111) surface. This is reflected in the electronic band structure, where the corrugation-induced splitting of the h-BN bands vanishes. In a second 3-pentanone exposure, a graphene layer is formed on the flat h-BN layer, evidenced by the appearance of the characteristic linear dispersion of its π band. The graphene layer grows incommensurate and highly oriented. The formation of graphene/h-BN on rhodium opens the door to scalable production of well-aligned heterostacks since single-crystalline thin-film Rh substrates are available in large dimensions.