BACKGROUND The use of microorganisms in remediating environmental contaminants such as crude oil sludge has become a promising technique owing to its economy and the fact it is environmentally friendly. Polycyclic aromatic hydrocarbons (PAHs), as the major components of oil sludge, are hydrophobic and recalcitrant. An important way of enhancing the rate of PAH desorption is to compost crude oil sludge by incorporating commercial surfactants, thereby making them available for microbial degradation. In this study, crude oil sludge was composted for 16 weeks during which surfactants were added in the form of a solution. RESULTS Molecular characterisation of the 16S rRNA genes indicated that the isolates obtained on a mineral salts medium belonged to different genera, including Stenotrophmonas, Pseudomonas, Bordetella, Brucella, Bacillus, Achromobacter, Ochrobactrum, Advenella, Mycobacterium, Mesorhizobium, Klebsiella, Pusillimonas and Raoultella. The percentage degradation rates of these isolates were estimated by measuring the absorbance of the 2,6-dichlorophenol indophenol medium. Pseudomonas emerged as the top degrader with an estimated percentage degradation rate of 73.7% after 7 days of incubation at 28 °C. In addition, the presence of the catabolic gene, catechol-2,3-dioxygenase was detected in the bacteria isolates as well as in evolutionary classifications based on phylogeny. CONCLUSIONS The bacteria isolated in this study are potential agents for the bioremediation of crude oil sludge.