The sulfur of coal limits its clean utilization, while the biodesulfurization technology shows great development potential and application prospects for coal desulfurization. With a view to studying the different sulfur metabolism preferences of bacteria, two‐step bioleaching desulfurization of coal was proposed in this paper in which the organic sulfur desulfurizing bacteria and inorganic sulfur oxidizing bacteria were, respectively, used to remove sulfur from coal. An organic sulfur desulfurizing strain, Rhodococcus erythropolis SX‐12, was isolated from petroleum‐polluted soil collected from the Daqing Oilfield, which has been discovered to be capable of degrading dibenzothiophene (DBT) with an optimum temperature of 30°C and an initial pH of 7.0. Rhodococcus erythropolis SX‐12, as organic sulfur desulfurizing bacteria, were employed for the first step bioleaching desulfurization. Laboratory‐preserved Acidithiobacillus ferrooxidans GF, an inorganic sulfur oxidizing strain, was applied to second step bioleaching desulfurization. After conducting two‐step bioleaching, the sulfur content of the raw coal decreased from 4.973% to 1.729% and the total desulfurization rate of 65.23% was obtained after 30‐day incubation. Therefore, the “two‐step” leaching biodesulfurization test is more likely to provide a new strategy for the process design of biodesulfurization of coal.