Successful cementing relies on the effective removal of oil-based muds (OBMs), especially from rock and casing surfaces. However, most OBMs are heavily absorbed onto the mineral surfaces as well as casing, deteriorating the interfacial bonding of cement to these surfaces. We present a novel cement additive using graphite nanoplatelets (GNPs) to minimize the impact of mud residuals on the bonding strengths of cement. To benefit from the individual superior mechanical properties of GNPs, we develop surface modification techniques to modify their surface properties and make them compatible with the aqueous medium of cement. Surface treatment of GNPs is critical to provide a uniform dispersion of them within the cementitious matrix and also create a strong interfacial bonding between them and cement hydrates. A series of push-out tests are conducted to evaluate how the addition of surface-modified GNPs affects the bonding strength at the cement/rock interfaces corresponding to different scenarios of OBM residues. The effect of different kinds of rocks, including sandstone, limestone, and shale, is also incorporated in the push-out tests. The experimental results show that after spacer flushing for the cases of limestone and sandstone cores, treated GNPs not only limit the impact of mud residuals at the interfaces but also raise the bonding strength beyond that corresponding to water saturated cores by about 357% and 194%, respectively. For the case of shale after spacer flushing, the bonding strength recovers about 70% as compared to the water saturated cores, and this strength is about 429% higher than that measured for the water saturated case when cement is plain (without surface-modified GNPs).