A typical tropical soil from the northeast of Brazil, where an important terrestrial oil field is located, was accidentally contaminated with a mixture of oil and saline production water. To study the bioremediation potential in this area, molecular methods based on PCR-DGGE were used to determine the diversity of the bacterial communities in bulk and in contaminated soils. Bacterial fingerprints revealed that the bacterial communities were affected by the presence of the mixture of oil and production water, and different profiles were observed when the contaminated soils were compared with the control. Halotolerant strains capable of degrading crude oil were also isolated from enrichment cultures obtained from the contaminated soil samples. Twenty-two strains showing these features were characterized genetically by amplified ribosomal DNA restriction analysis (ARDRA) and phenotypically by their colonial morphology and tolerance to high NaCl concentrations. Fifteen ARDRA groups were formed. Selected strains were analyzed by 16S rDNA sequencing, and Actinobacteria was identified as the main group found. Strains were also tested for their growth capability in the presence of different oil derivatives (hexane, dodecane, hexadecane, diesel, gasoline, toluene, naphthalene, o-xylene, and p-xylene) and different degradation profiles were observed. PCR products were obtained from 12 of the 15 ARDRA representatives when they were screened for the presence of the alkane hydroxylase gene (alkB). Members of the genera Rhodococcus and Gordonia were identified as predominant in the soil studied. These genera are usually implicated in oil degradation processes and, as such, the potential for bioremediation in this area can be considered as feasible.