The emission of sulfur oxides can have adverse effects on the environment. Biodesulfurization of fossil fuels is attracting more and more attention because such a bioprocess is environmentally friendly. Some techniques of desulfurization have been used or studied to meet the stricter limitation on sulfur content in China. Recent advances have demonstrated the mechanism and developments for biodesulfurization of gasoline, diesel and crude oils by free cells or immobilized cells. Genetic technology was also used to improve sulfur removal efficiencies. In this review, we summarize recent progress mainly in China on petroleum biodesulfurization.