For the production of oil-desulfurizing biocatalyst, a two-stage fermentation strategy was adopted, in which the cell growth stage and desulfurization activity induction stage were separated. Sucrose was found to be the optimal carbon source for the growth of Gordonia nitida CYKS1. Magnesium sulfate was selected to be the sulfur source in the cell growth stage. The optimal ranges of sucrose and magnesium sulfate were 10-50 and 1-2.5 g L-1, respectively. Such a broad optimal concentration of sucrose made the fed-batch culture easy, while the sucrose concentration was maintained between 10-20 g L-1 in the actual operation. As a result, 92.6 g L-1 of cell mass was acquired by 120 h of fed-batch culture. This cell mass was over three times higher than a previously reported result, though the strain used was different. The desulfurization activity of the harvested cells from the first stage culture was induced by batch cultivation with dibenzothiophene as the sole sulfur source. The optimal induction time was found to be about 4 h. The resting-cell biocatalyst made from the induced cells was applied for the deep desulfurization of a diesel oil. It was observed that the sulfur content of the diesel oil decreased from 250 mg-sulfur L-oil-1 to as low as 61 mg-sulfur L-oil-1 in 20 h. It implied that the biocatalyst developed in this study had a good potential to be applied to a deep desulfurization process to produce ultra-low-sulfur fuel oils.