Molecular characterization of the microbial populations of soils and sediments contaminated with polycyclic aromatic hydrocarbons (PAHs) is often a first step in assessing intrinsic biodegradation potential. However, soils are problematic for molecular analysis owing to the presence of organic matter, such as humic acids. Furthermore, the presence of contaminants, such as PAHs, can cause further challenges to DNA extraction, quantification, and amplification. The goal of our study was to compare the effectiveness of four commercial soil DNA extraction kits (UltraClean Soil DNA Isolation kit, PowerSoil DNA Isolation kit, PowerMax Soil DNA Isolation kit, and FastDNA SPIN kit) to extract pure, high-quality bacterial and eukaryotic DNA from PAH-contaminated soils. Six different contaminated soils were used to determine if there were any biases among the kits due to soil properties or level of contamination. Extracted DNA was used as a template for bacterial 16S rDNA and eukaryotic 18S rDNA amplifications, and PCR products were subsequently analyzed using denaturing gel gradient electrophoresis (DGGE). We found that the FastDNA SPIN kit provided significantly higher DNA yields for all soils; however, it also resulted in the highest levels of humic acid contamination. Soil texture and organic carbon content of the soil did not affect the DNA yield of any kit. Moreover, a liquid–liquid extraction of the DNA extracts found no residual PAHs, indicating that all kits were effective at removing contaminants in the extraction process. Although the PowerSoil DNA Isolation kit gave relatively low DNA yields, it provided the highest quality DNA based on successful amplification of both bacterial and eukaryotic DNA for all six soils. DGGE fingerprints among the kits were dramatically different for both bacterial and eukaryotic DNA. The PowerSoil DNA Isolation kit revealed multiple bands for each soil and provided the most consistent DGGE profiles among replicates for both bacterial and eukaryotic DNA.