High production of Rhodococcus erythropolis LSSE8-1 and its application for the treatment of diesel oils was investigated. Culture conditions were optimized by Taguchi orthogonal array experimental design methodology. High cell density cultivation of biocatalyst with pH control and fed-batch feeding strategies was further validated in a fermentor with the optimal factors. Cell concentration of 23.9 g dry cells/L was obtained after 96 h cultivation. The resting cells and direct fermentation suspension were applied for deep desulfurization of hydrodesulfurized diesel oils. It was observed that the sulfur content of the diesel decreased from 248 to 51 μg/g by two consecutive biodesulfurizations. It implied that the biodesulfurization process can be simplified by directly mixing cell cultivation suspension with diesel oil. The biocatalyst developed with the Taguchi method has the potential to be applied to produce ultra-low-sulfur petroleum oils.