A very rich Fe-C phase diagram makes the formation of graphene on iron surfaces a challenging task. Here we demonstrate that the growth of graphene on epitaxial iron films can be realized by chemical vapor deposition at relatively low temperatures, and that the formation of carbides can be avoided in excess of the carbon-containing precursors. The resulting graphene monolayer creates a novel periodically corrugated pattern on Fe(110). Using low-energy electron microscopy and scanning tunneling microscopy, we show that it is modulated in one dimension forming long waves with a period of ∼4  nm parallel to the 001 direction of the substrate, with an additional height modulation along the wave crests. The observed topography of the graphene/Fe superstructure is well reproduced by density functional theory calculations, and found to result from a unique combination of the lattice mismatch and strong interfacial interaction, as probed by core-level photoemission and x-ray absorption spectroscopy.