2D metal-organic networks show great promise for applications in catalysis, gas sensing or electronics. Ascertaining fundamental intrinsic properties of such systems requires their synthesis on weakly-interacting substrates. Here, we show Fe-TCNQ networks self-assembled on graphene/Ir(111), studied experimentally by Low Energy Electron Microscopy (LEEM), Scanning Tunneling Microscopy (STM) and X-Ray Photoemission Spectroscopy (XPS). A single Fe-TCNQ structure is present in three non-equivalent orientations on the graphene substrate; symmetry operations lead to observation of fifteen rotational domains. The network is thermally stable up to ca. 550 °C, making this an ideal model system for fundamental studies of single-atom reactivity or charge transfer induced phenomena.