A cobalt-based polyoxometalate, (STA)₁₀[Co₄(H₂O)₂(PW₉O₃₄)₂] (SEP) (STA = stearyltrimethylammonium), was prepared by ionic exchange of K₁₀[Co₄(H₂O)₂(PW₉O₃₄)₂] and STA·Cl. SEP was approved as an effective catalyst for desulfurization of fuels in [Bmim]PF₆ by using aqueous H₂O₂ as oxidant in an extraction and catalytic oxidative desulfurization system (ECODS). The optimum desulfurization conditions were obtained: DBT could be completely removed with only O/S molar ratio of 4 in 40 min at 60 °C in a three-liquid-phase micro-emulsion system. The catalyst could be recycled conveniently and reused at least six times without significantly reducing the desulfurization efficiency. Therefore, this catalyst shows excellent regeneration and a good prospect for industrial application. For different substrates, the efficiencies of sulfur removal decreased in the following order: DBT > 4,6-DMDBT > BT under the same conditions. Furthermore, the catalytic oxidation desulfurization mechanism of SEP was studied.