Petroleum sludge contains polycyclic aromatic hydrocarbons (toxic and carcinogenic-mutagenic compounds) and heavy metals. It needs to be suitably treated and disposed in an environmental friendly fashion. This paper reports the effectiveness of additives (Ca(OH)2 and NaHCO3) and excess air in thermal treatment of petroleum sludge cake and the suitability of the residual of Petroleum SludgeAsh (PSA) as a Cement Replacement Material (CRM). Polycyclic Aromatic Hydrocarbons (PAH) concentrations in samples were determined using GC-MS. Leaching of heavy metals from petroleum sludge cake and PSA was determined following TCLP. Heavy metals concentrations were determined using AAS. Mortar mixes were prepared with different amounts of cement replacement by PSA and their compressive strengths were determined. Additives and excess air were found to improve sludge treatment. The strength development of mortar cubes showed that PSA has the potential to be used as CRM. The studied treatment method provides a solution that also enhances sustainability. © 2016 Taylor & Francis Group, London.