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 32OW 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.