MXenes with versatile chemistry and superior electrical conductivity are prevalent candidate materials for energy storage and catalysts. Inspired by recent experiments of hybridizing MXenes with carbon materials, here we theoretically design a series of heterostructures of N-doped graphene supported by MXene monolayers as bifunctional electrocatalysts for the oxygen reduction reaction (ORR) and hydrogen evolution reaction (HER). Our first-principles calculations show that the graphitic sheet on V2C and Mo2C MXenes are highly active with an ORR overpotential down to 0.36 V and reaction free energies for the HER approaching zero, both with low kinetic barriers. Such outstanding catalytic activities originate from the electronic coupling between the graphitic sheet and the MXene, and can be correlated with the pz band center of surface carbon atoms and the work function of the heterostructures. Our findings screen a novel form of highly active electrocatalysts by taking advantage of the fast charge transfer kinetics and strong interfacial coupling of MXenes, and illuminate a universal mechanism for modulating the catalytic properties of two-dimensional hybrid materials.