The dynamics of catalase activity of the hydrocarbon-oxidizing bacteria Cordona terrae, Rhodococcus rubropertinctus, and Rhodococcus erythropolis during petroleum product destruction has been studied. A direct relationship between decreasing catalase activity of hydrocarbon-oxidizing microorganisms and the intensity of petroleum product destruction has been established experimentally. The revealed dependence allows one to consider the catalase activity of bacteria as an indicator of the initial stage of petroleum product oxidation and may be used for choosing destructor strains to construct biopreparations suitable for natural ecosystem remediation.