Sulfur metabolism in fuel-biodesulfurizing bacteria and the underlying physiological adaptations are not understood, which has impeded the development of a commercially viable bioprocess for fuel desulfurization. To fill these knowledge gaps, we performed comparative proteomics and untargeted metabolomics in cultures of the biodesulfurization reference strain Rhodococcus qingshengii IGTS8 grown on either inorganic sulfate or the diesel-borne organosulfur compound dibenzothiophene as a sole sulfur source. Dibenzothiophene significantly altered the biosynthesis of many sulfur metabolism proteins and metabolites in a growth phase-dependent manner, which enabled us to reconstruct the first experimental model for sulfur metabolism in a fuel-biodesulfurizing bacterium. All key pathways related to assimilatory sulfur metabolism were represented in the sulfur proteome, including uptake of the sulfur sources, sulfur acquisition, and assimilatory sulfate reduction, in addition to biosynthesis of key sulfur-containing metabolites such as S-adenosylmethionine, coenzyme A, biotin, thiamin, molybdenum cofactor, mycothiol, and ergothioneine (low-molecular weight thiols). Fifty-two proteins exhibited significantly different abundance during at least one growth phase. Sixteen proteins were uniquely detected and 47 proteins were significantly more abundant in the dibenzothiophene culture during at least one growth phase. The sulfate-free dibenzothiophene-containing culture reacted to sulfate starvation by restricting sulfur assimilation, enforcing sulfur-sparing, and maintaining redox homeostasis. Biodesulfurization triggered alternative pathways for sulfur assimilation different from those operating in the inorganic sulfate culture. Sulfur metabolism reprogramming and metabolic switches in the dibenzothiophene culture were manifested in limiting sulfite reduction and biosynthesis of cysteine, while boosting the production of methionine via the cobalamin-independent pathway, as well as the biosynthesis of the redox buffers mycothiol and ergothioneine. The omics data underscore the key role of sulfur metabolism in shaping the biodesulfurization phenotype and highlight potential targets for improving the biodesulfurization catalytic activity via metabolic engineering.