In order to further reduce the sulfur content in gasoline, a new desulfurization process was proposed by using catalytic oxidation and extraction realized in an electrochemical fluidized reactor. The fluidized layer of loaded catalyst particles consisted of lead dioxide (PbO2) supported on activated carbon particles (PbO2/C) and the electrolyte was aqueous NaOH solution. The PbO2/C particle anodes could remarkably accelerate the electrochemical reaction rate and promote the electrochemical catalysis of sulfur compounds. The sulfur compounds were at first oxidized to sulfones or sulfoxides, which were then removed after extraction. The experimental results indicated that the optimal desulfurization conditions were as follows: The cell voltage was 3.2 V, the concentration of hydroxyl ions in electrolyte was 0.12 mol/L, and the feed rate was 300 mL/min. Under these conditions the concentration of sulfur in gasoline was reduced from 310 ppm to 70 ppm. Based on these experimental results, a mechanism of indirect electrochemically catalytic oxidation was proposed.