The use of indigenous bacterial strains is a valuable bioremediation strategy for cleaning the environment from hydrocarbon pollutants. The isolation and selection of hydrocarbon-degrading bacteria is therefore crucial for obtaining the most promising strains for site decontamination. Two different media, a minimal medium supplemented with a mixture of polycyclic aromatic hydrocarbons and a MS medium supplemented with triphenyltetrazolium chloride, were used for the isolation of bacterial strains from two hydrocarbon contaminated soils and from their enrichment phases. The hydrocarbon degradation abilities of these bacterial isolates were easily and rapidly assessed using the 2,6-dichlorophenol indophenol assay. The diversity of the bacterial communities isolated from these two soil samples and from their enrichment phases was evaluated by the combination of a bacterial clustering method, fluorescence ITS-PCR, and bacterial identification by 16S rRNA sequencing. Different PCR-based assays were performed in order to detect the genes responsible for hydrocarbon degradation. The best hydrocarbon-degrading bacteria, including Arthrobacter sp., Enterobacter sp., Sphingomonas sp., Pseudomonas koreensis, Pseudomonas putida and Pseudomonas plecoglossicida, were isolated directly from the soil samples on minimal medium. The nahAc gene was detected only in 13 Gram-negative isolates and the sequences of nahAc-like genes were obtained from Enterobacter, Stenotrophomonas, Pseudomonas brenneri, Pseudomonas entomophila and P. koreensis strains. The combination of isolation on minimal medium with the 2,6-dichlorophenol indophenol assay was effective in selecting different hydrocarbon-degrading strains from 353 isolates.