Abstract Aims Biodesulfurization of fossil fuels is a promising technology for deep desulfurization. Previously, we have shown that Paenibacillus strains 32O-W and 32O-Y can desulfurize dibenzothiophene (DBT) and DBT sulfone (DBTS) effectively. In this work, improvements in DBT and DBTS desulfurization by these strains were investigated through immobilization and nanoparticle coating of cells. Methods and Results Paenibacillus strains 32O-W and 32O-Y immobilized in alginate gel beads or coated with Fe3O4 magnetite nanoparticles were grown at various concentrations (0.1–2 mmol l−1) of DBT or DBTS for 96 h. The production of 2-hydroxybiphenyl (2-HBP) from the 4S pathway biotransformation of DBT or DBTS was measured. The highest amounts of 2-HBP production occurred at concentrations of 0.1 and 0.5 mmol l−1. Compared to planktonic cultures maximum 2-HBP production increased by 54% for DBT and 90% for DBTS desulfurization with immobilized strains, and 44% for DBT and 66% for DBTS desulfurization by nanoparticle-coated strains. Conclusions Nanoparticle-coated and immobilized cells may be of use in efforts to increase the efficiency of biodesulfurization. Significance and Impact of the Study Alginate immobilization or nanoparticle coating of bacterial cells may be useful approaches for the enhancement of biodesulfurization for eventual use on an industrial scale.