One of the main precursors of air pollution and acid rains is the presence of the recalcitrant thiophenic compounds, for example dibenzothiophene (DBT) and its derivatives in transportation fuels. In an attempt to achieve the worldwide regulations of ultra-low sulfur transportation fuels without affecting its hydrocarbon skeleton, a biphasic medium containing 100 mg/L DBT dissolved in n-hexadecane (1/4 oil/water v/v) used for enrichment and isolation of selective biodesulfurizing bacterium from an oil-polluted sediment sample collected from Egyptian Red Sea shoreline. The isolated bacterium is facultative anaerobe, motile, spore-former, and mesophile. It is genetically identified asPaenibacillus glucanolyticusstrain HN4 (NCBI Gene Bank Accession No. MT645230). HN4 desulfurized DBT as a model of the recalcitrant thiophenic compounds without affecting its hydrocarbon skeleton via the 4S-pathway producing 2-hydroxybiphenyl (2-HBP) as a dead end product. HN4 substantiated to be a hydrocarbon tolerant, biosurfactants(s) producer, and endorsed unique enzymatic system capable of desulfurizing broad range of thiophenic compounds and expressed an efficient desulfurization activity against the recalcitrant alkylated DBTs. As far our knowledge, it is the first reported BDS study usingP. glucanolyticus. Statistical optimization based on One-Factor-At-A-Time (OFAT) technique and response surface methodology (RSM) applied for elucidation of mathematical model correlations describing and optimizing the effect of different physicochemical parameters on batch biphasic BDS process. That illustrated an approximate increase in BDS efficiency by 1.34 fold and recorded 94% sulfur removal in biphasic batch process at optimum operation conditions of 120 h, 0.14 wt% S-content model oil (DBT dissolved in n-hexadecane), 33.5 degrees C, pH7 and 1/1 oil/water phase ratio, and 147 rpm. Resting cells of HN4 in a biphasic reactor (1/1 v/v) decreased the sulfur content of a refractory thiophenic model oil (thiophene, benzothiophene, DBT, and alkylated DBT dissolved in n-hexadecane) from 0.14 to 0.027 wt%, and petro-diesel from 0.2 to 0.04 wt%, within 120 h, keeping the calorific value of the treated fuel intact. Consequently, that novel strain could be recommended as a promising candidate for BDS as complementary to hydrodesulfurization process in oil refinery.