Oil refineries are facing many challenges, including heavier crude oils, increased fuel quality standards, and a need to reduce air pollution emissions. Global society is stepping on the road to zero-sulfur fuel, with only differences in the starting point of sulfur level and rate reduction of sulfur content between different countries. Hydrodesulfurization (HDS) is the most common technology used by refineries to remove sulfur from intermediate streams. However, HDS has several disadvantages, in that it is energy intensive, costly to install and to operate, and does not work well on refractory organosulfur compounds. Recent research has therefore focused on improving HDS catalysts and processes and also on the development of alternative technologies. Among the new technologies one possible approach is biocatalytic desulfurization (BDS). The advantage of BDS is that it can be operated in conditions that require less energy and hydrogen. BDS operates at ambient temperature and pressure with high selectivity, resulting in decreased energy costs, low emission, and no generation of undesirable side products. Over the last two decades several research groups have attempted to isolate bacteria capable of efficient desulfurization of oil fractions. This review examines the developments in our knowledge of the application of bacteria in BDS processes, assesses the technical viability of this technology and examines its future challenges.