A process for removing carbonaceous deposits on surfaces of catalysts and plant parts by treating the deposits with a superheated stream of steam admixed at least temporarily with an oxygenous gas is provided, which involves, in each case monitoring the offgas CO2 content after condensation of the steam, at a temperature of at least 300° C.: (a) treating the carbonaceous deposits with superheated steam at a temperature of at least 300° C. until the CO2 content of the offgas has exceeded a maximum; (b) then, with further supply of superheated steam, commencing oxygen supply, the amount of oxygen supplied being adjusted such that the CO2 content in the offgas decreases further until it has fallen to a value of