Extractive-catalytic oxidative desulfurization (ECOD) technology is a potential industrial application for attaining low-sulfur fuel oils. In this research, novel graphene oxide (GO)-based heterogeneous catalysts were synthesized by immobilization of different amounts of phosphotungstic acid H3PW12O40 (HPW) on GO. The obtained HPW-GO catalysts were characterized by FT-IR, SEM, EDX, TEM, AFM, and RAMAN analyses. The ECOD was applied for removal of dibenzothiophene (DBT) from a model fuel with H2O2 as the oxidant, acetonitrile as the extracting solvent, and HPW-GOs as the catalysts. Among the catalysts with different HPW contents (5, 10, 20, 25, 30, 40 wt%), the catalyst with 40 wt% HPW had the best performance. The optimum reaction time, temperature, H2O2/sulfur molar ratio (O/S) as well as the kinetic parameters (kinetic constants and apparent activation energy) were evaluated. 100 percent desulfurization yield was achieved in a short time (t= 30 min) using the 40 wt% catalyst under moderate conditions (catalyst loading= 5 g/l, O/S= 6, T= 333 K). Aiding by synergism, the heterogeneous HPW-GO catalyst showed a higher desulfurization yield compared to that by the homogeneous HPW. The reactivity of 4,6-dimethyldibenzothiophene (4,6-DMDBT) in the ECOD process was found to be equal to that of DBT but much higher than the reactivity of benzothiophene (BT) within 60 min. The catalyst could be recycled for eight times without significant decrease in activity. A reasonable reaction pathway was proposed based on the GC-MS analysis. Almost all of the sulfur content of a real fuel could be completely oxidized and removed by the ECOD. Comparing to the results reported in literature, the features of proposed one-step fast ECOD process, which requires very low catalyst at moderate conditions for complete desulfurization without any phase transfer agent, makes it distinctive for practical applications.