The sulfur in petroleum coke is harmful to carbon products, underscoring the importance of desulfurization for high-sulfur petroleum coke. This paper proposes a method combining alkaline catalytic roasting with ultrasonic oxidation for the deep desulfurization of high-sulfur petroleum coke. The results show that the desulfurization rate reaches 88.99% and the sulfur content is reduced to 0.83 wt.% under a coke particle size of 96–75 μm, sodium-hydroxide-to-petroleum-coke ratio of 50%, roasting temperature of 700 °C, and holding time of 2 h. The alkali-calcined petroleum coke is ultrasonically oxidized and desulfurized in peracetic acid. The results show that, under a hydrogen peroxide content of 10%, hydrogen-peroxide-(liquid)-to-petroleum-coke (solid) ratio of 20 mL/g, acetic acid content of 5 mL, ultrasonic power of 300 W, reaction temperature of 60 °C, and reaction duration of 4 h, the sulfur content is reduced to 0.15 wt.% and the total desulfurization reaches 98.01%. Through a series of characterizations, the proposed desulfurization mechanism is verified. Alkali roasting effectively removes a significant portion of sulfur in petroleum coke. However, the elimination of certain sulfur compounds, such as the more complex thiophene, presents challenges. The thiophene content is subsequently removed via ultrasonic oxidation.