The ability of 96 microbial strains degrading oil and 32 strains degrading polycyclic aromatic hydrocarbons (PAHs) to consume diesel fuel and oil at 4–6 and 24°C and at elevated NaCl concentrations was studied. The temperature range, salt tolerance, ability to produce biosurfactants, range of substrates, and antibiotic resistance were determined. The eleven most active oil-degrading and PAH-degrading strains were genotyped by a polymerase chain reaction with BoxA1R primers and a restriction analysis of ribosomal DNA amplicons. For six strains, the degree of oil degradation at 4–6°C was higher than at 24°C. For the most active strains, the degree of oil degradation in liquid mineral medium ranged from 15 to 26% at 24°C and from 28 to 47% at 4–6°C. An association of six of the strains degraded the oil by 46% at 24°C.