Abstract: MXenes are the newest class of two-dimensional (2D) materials, and they offer great potential in a wide range of applications including electronic devices, sensors, and thermoelectric and energy storage materials. In this work, we combined the outstanding electrical conductivity, that is essential for battery applications, of graphene with MXene monolayers (M2CX2 where M = Sc, Ti, V and X = OH, O) to explore its potential in Li battery applications. Through first principles calculations, we determined the stable stacking configurations of M2CX2/graphene bilayer heterostructures and their Li atom intercalation by calculating the Li binding energy, diffusion barrier and voltage. We found that: (1) for the ground state stacking, the interlayer binding is strong, yet the interlayer friction is small; (2) Li binds more strongly to the O-terminated monolayer, bilayer and heterostructure MXene systems when compared with the OHterminated MXenes due to the H+ induced repulsion to the Li atoms. The binding energy of Li decreases as the Li concentration increases due to enhanced repulsive interaction between the positively charged Li ions; (3) Ti2CO2/graphene and V2CO2/graphene heterostructures exhibit large Li atom binding energies making them the most promising candidates for battery applications. When fully loaded with Li atoms, the binding energy is -1.43 eV per Li atom and -1.78 eV per Li atom for Ti2CO2/graphene and V2CO2/graphene, respectively. These two heterostructures exhibit a nice compromise between storage capacity and kinetics. For example, the diffusion barrier of Li in Ti2CO2/graphene is around 0.3 eV which is comparable to that of graphite. Additionally, the calculated average voltages are 1.49 V and 1.93 V for Ti2CO2/graphene and V2CO2/graphene structures, respectively; (4) a small change in the in-plane lattice parameters (<1%), interatomic bond lengths and interlayer distances (<0.5 angstrom) proves the stability of the heterostructures against Li intercalation, and the impending phase separation into constituent layers and capacity fading during charge-discharge cycles in real battery applications; (5) as compared to bare M2CX2 bilayers, M2CX2/graphene heterostructures have lower molecular mass, offering high storage capacity; (6) the presence of graphene ensures good electrical conductivity that is essential for battery applications. Given these advantages, Ti2CO2/graphene and V2CO2/graphene heterostructures are predicted to be promising for lithium-ion battery applications.