Graphene is grown by chemical vapour deposition on ruthenium ultrathin films down to a nominal thickness of 5 nm. While at 910 degrees C multilayer graphitic films are obtained, single layer defective graphene is formed at 1000 degrees C. The extremely thin Ru films allow the formation of a novel nano-crystalline ruthenium carbide phase to be discerned by combining synchrotron X-ray diffraction, synchrotron X-ray absorption spectroscopy and electron diffraction. The ruthenium carbide (Ru-C) phase formed at or above 1000 degrees C presents cubic symmetry (cP) with a lattice parameter of 2.927 angstrom and a Ru-C distance of around 2.31 angstrom. The increase of C solubility in ruthenium seems to be sufficient to trigger the stabilization of the Ru-C phase during graphene growth preferentially in grains with orientation different to (0001). The structural transition from hcp Ru to cP Ru-C is not limited to a shell; it occurs for the whole grain. The formation of the carbide seems to favour the synthesis of single layer graphene by hindering the segregation of carbon to the surface during cooling. This simple method allows nano-crystalline ruthenium-carbide films to be obtained as well as graphene covered Ru nanograins, both with size control. These new materials are foreseen to present interesting mechanical, catalytic and sensing properties.