This work explores the effectiveness of Portland cement (CEM I), with the addition of high carbon fly ash (HCFA), as a novel binder, for the improvement of leachability-related properties of stabilized/solidified (s/s) petroleum drill cuttings. A factorial design experiment was adopted to investigate the effects of waste-to-binder ratio, HCFA addition, and curing time on leachate pH, acid neutralization capacity (ANC), and metal, chloride and hydrocarbon leaching. The leachate pH and ANC of all products suggested successful formation of a calcium-silicate-hydrate-based matrix with good resistance to acid attack, and little detrimental effect from drill cuttings addition. Leaching of amphoteric metals was significantly affected by pH, which was a function of other studied factors. All studied factors also affected leaching of chloride and hydrocarbons. CEM I, without HCFA addition, was more effective in immobilizing chlorides, but the overall chloride immobilization was poor in all runs. HCFA addition significantly reduced the leaching of hydrocarbons. Comparison of milligram of contaminant leached per kilogram of drill cuttings from the s/s products and untreated drill cuttings provided clear evidence of hydrocarbon and chloride immobilization. This work shows that HCFA improved the immobilization of organic contaminants and may represent an inexpensive binder for stabilization/solidification of organic wastes.