Oil and phenol spills resulting from human activity cause serious harm to the environment and public health. Soil permeability is impaired, salinization worsens significantly, and pH levels are altered. Bacterial isolates with high degradative activity are most often recovered from samples regularly contaminated with toxicants. The purpose of this study was to characterize degradative potential of two strains isolated from oil sludge using the enrichment cultivation method, identified by the 16S rRNA gene as Stutzerimonas stutzeri. The concentration of petroleum products was measured using IR-spectrophotometry. The amount of phenol was estimated using a calibration graph reflecting the dependence of phenol concentration on absorption at 270 nm. The ability to grow under elevated salinity was determined by cultivation in GRM broth supplemented with sodium chloride. Strains were capable of degrading crude oil. The loss of petroleum products amounted to 24% and 25.6% for St. stutzeri T2/b and St. stutzeri T1/zh, respectively, over a 21-day exposure period at 30°C. Both bacteria were able to use phenol at a concentration of 1 g/L as the sole source of carbon and energy, as the phenol concentration increased to 1.5 g/L, biomass growth slowed, but the strain cells remained viable. Isolates were found to be able to thrive at temperature +50 ℃ and in salinity levels up to 10%. To prevent the potential acquisition of antibiotic resistance genes, present in the biopreparations used by the endogenous microflora, the antibiotic resistance of the isolated strains was investigated. Strains were found to be susceptible to most used antibiotics tested. The results obtained in this study have significantly expanded knowledge regarding the degradative activity of Stutzerimonas stutzeri. These strains capable of degrading phenol, petroleum, and petroleum components can be used for environmental remediation under adverse climatic conditions, including high salinity (70–100 g/L) and temperatures up to 50°C.