New desulfurizing bacteria able to convert dibenzothiophene into 2-hydroxybiphenyl and sulfate were isolated from contaminated soils collected in Mexican refineries. Random amplified polymorphic DNA analysis showed they were different from previously reported Rhodococcus erythropolis desulfurizing strains. According to 16S rRNA gene sequencing and fatty acid analyses, these new isolates belonged to the genus Rhodococcus. These strains could desulfurize 4,6-dimethyldibenzothiophene which is one of the most difficult dibenzothiophene derivatives to remove by hydrodesulfurization. A deeply hydrodesulfurized diesel oil containing significant amounts of 4,6-dimethyldibenzothiophene was treated with Rhodococcus sp. IMP-S02 cells. Up to 60% of the total sulfur was removed and all the 4,6-dimethyldibenzothiophene disappeared as a result of this treatment.