Abstract: Bacillus sp. -02 and Bacillus sp. -12 produced Optical Density (OD) readings of 1.228 and 0.540 , respectively at 540 nm wavelength during screen tests in crude oil/mineral salts broth medium. In addition, both organisms caused extensive shredding (breakdown) of the overlaid oil in tubes indicating oil utilization. Gravimetric measurement of hydrocarbonoclastic potentials of the organisms revealed that such potentials were similar in both species (49.8 and 48.6% weight losses , respectively). Carbon dioxide evolution studies under the influences of cadmium toxicity at concentrations of 1, 10, 100 and 1000 mg L-1 and pH changes from 5.5 through 7.0 to 8.5, revealed that Bacillus sp. -12 produced higher amounts of CO2 and was less sensitive to cadmium toxicity and pH changes during the process than Bacillus sp.-02. This shows that Bacillus sp.-12 would be useful in the bioremediation of petroleum-polluted environments co-contaminated with cadmium in the Niger Delta region of Nigeria.