This article presents a study of the efficiency and degradation pattern of samples of petroleum sludge and polluted sandy soil from an oil refinery. A bacterial consortium, consisting of strains from the genera Pseudomonas, Achromobacter, Bacillus and Micromonospora, was isolated from a petroleum sludge sample and characterized. The addition of nitrogen and phosphorus nutrients and a chemical surfactant to both the samples and bioaugmentation to the soil sample were applied under laboratory conditions. The extent of biodegradation was monitored by the gravimetric method and analysis of the residual oil by gas chromatography. Over a 12-week experiment, the achieved degree of TPH (total petroleum hydrocarbon) degradation amounted to 82-88% in the petroleum sludge and 86-91% in the polluted soil. Gas chromatography-mass spectrometry was utilized to determine the biodegradability and degradation rates of n-alkanes, isoprenoids, steranes, diasteranes and terpanes. Complete degradation of the n-alkanes and isoprenoids fractions occurred in both the samples. In addition, the intensities of the peaks corresponding to tricyclic terpenes and homohopanes were decreased, while significant changes were also observed in the distribution of diasteranes and steranes.