Microbial desulfurization or biodesulfurization (BDS) is an attractive low-cost and environmentally friendly complementary technology to the hydrotreating chemical process based on the potential of certain bacteria to specifically remove sulfur from S-heterocyclic compounds of crude fuels that are recalcitrant to the chemical treatments. The 4S or Dsz sulfur specific pathway for dibenzothiophene (DBT) and alkyl-substituted DBTs, widely used as model S-heterocyclic compounds, has been extensively studied at the physiological, biochemical and genetic levels mainly in Gram-positive bacteria. Nevertheless, several Gram-negative bacteria have been also used in BDS because they are endowed with some properties, e.g., broad metabolic versatility and easy genetic and genomic manipulation, that make them suitable chassis for systems metabolic engineering strategies. A high number of recombinant bacteria, many of which are Pseudomonas strains, have been constructed to overcome the major bottlenecks of the desulfurization process, i.e., expression of the dsz operon, activity of the Dsz enzymes, retro-inhibition of the Dsz pathway, availability of reducing power, uptake-secretion of substrate and intermediates, tolerance to organic solvents and metals, and other host-specific limitations. However, to attain a BDS process with industrial applicability, it is necessary to apply all the knowledge and advances achieved at the genetic and metabolic levels to the process engineering level, i.e., kinetic modelling, scale-up of biphasic systems, enhancing mass transfer rates, biocatalyst separation, etc. The production of high-added value products derived from the organosulfur material present in oil can be regarded also as an economically viable process that has barely begun to be explored.