The manifestation of superconductivity in graphene has been the topic of numerous recent theoretical works, which predicted new behaviors in this 2D ballistic system where electrons are described by a relativistic equation. The integration of graphene into Josephson junctions has already shown that a superconducting current could be measured across the carbon layer, but the good quality of the interface between graphene and a superconductor remains very challenging and yet a key factor to study the superconducting proximity effect. We developed a new very efficient way to strongly couple graphene to a superconductor, by growing it directly on top of rhenium, which shows superconductivity below 2K. The graphene monolayer has been grown by a chemical vapor deposition process in a UHV chamber on epitaxial rhenium thin films of 30 nm thickness. The lattice parameters mismatch between graphene and Rhenium gives rise to a so-called moiré pattern that we characterized by scanning tunneling microscopy (STM, cf figure below) and simulated with ab initio calculations. The moiré supercell has a periodicity of 1.9nm +/- 0.1nm, which corresponds to eight carbon rings matching seven rhenium atoms. Our simulations show the valleys correspond to regions where the graphene interacts strongly with the underlying substrate while the hills correspond to weaker interacting regions. Spectroscopic measurements performed at 50mK revealed that the density of states around the Fermi energy is position dependent on the moiré and highlighted a homogeneous superconducting state of the graphene layer, well fitted by the standard Bardeen-Cooper-Schrieffer (cf figure below). All our results demonstrate a very good interface between graphene and the superconducting rhenium substrate, turning our system into a building block to design hybrid superconducting nanostructures, where the good transparency of the superconductor-normal metal interface is of primary importance.