Enhancement of the desulfurization activities of Paenibacillus strains 32O‐W and 32O‐Y were investigated using dibenzothiophene (DBT) and DBT sulfone (DBTS) as sources of sulphur in growth experiments. Strains 32O‐W, 32O‐Y and their co‐culture (32O‐W plus 32O‐Y), and Vitreoscilla hemoglobin (VHb) expressing recombinant strain 32O‐Yvgb and its co‐culture with strain 32O‐W were grown at varying concentrations (0·1–2 mmol l−1) of DBT or DBTS for 96 h, and desulfurization measured by production of 2‐hydroxybiphenyl (2‐HBP) and disappearance of DBT or DBTS. Of the four cultures grown with DBT as sulphur source, the best growth occurred for the 32O‐Yvgb plus 32O‐W co‐culture at 0·1 and 0·5 mmol l−1 DBT. Although the presence of vgb provided no consistent advantage regarding growth on DBTS, strain 32O‐W, as predicted by previous work, was shown to contain a partial 4S desulfurization pathway allowing it to metabolize this 4S pathway intermediate.