Exposure to crude oil in the presence of an initial brine saturation can render rocks mixed-wet. Subsequent exposure to components of synthetic oil-based drilling fluids can alter the wetting toward less water-wet or more oil-wet conditions. Mixing of the non-aromatic base oils used in synthetic oil-based muds (SBM) with an asphaltic crude oil can destabilize asphaltenes and make cores less water-wet. Wetting changes can also occur due to contact with the surfactants used in SBM formulations to emulsify water and make the rock cuttings oil-wet. Reservoir cores drilled with SBMs, therefore, show wetting properties much different from the reservoir wetting conditions, invalidating laboratory core analysis using SBM contaminated cores. Core cleaning is required in order to remove all the drilling mud contaminants. In theory, core wettability can then be restored to reservoir wetting conditions by exposure to brine and crude oil. The efficiency of core cleaning of SBM contaminated cores has been explored in this study. A new core cleaning procedure was developed aimed to remove the adsorbed asphaltenes and emulsifiers from the contaminated Berea sandstone cores. Sodium hydroxide was introduced into the cleaning process in order to create a strongly alkaline condition. The high pH environment in the pore spaces changed the electrical charges of both basic and acidic functional groups, reducing the attractive interactions between adsorbing materials and the rock surface. In cores, flow-through and extraction methods were investigated. The effectiveness of the cleaning procedure was assessed by spontaneous imbibition tests and Amott wettability measurements. Test results indicating that introduction of sodium hydroxide played a key role in removing adsorbed materials were confirmed by contact angle measurements on similarly treated mica surfaces. Cleaning of the contaminated cores reversed their wettability from oil-wet to strongly water-wet as demonstrated by spontaneous imbibition rates and Amott wettability indices.