This work describes a new method for extracting genomic DNA from heavy oil-contaminated soils. This method combines soil washes using three washing solutions with enzymatic lysis (SW-EL method). The suitability of the SW-EL method was validated by extracting DNA from samples as small as 0.5 g from model microcosms comprising soil artificially contaminated with 1 and 10% (w/w) heavy petroleum and seeded with a bacterial consortium. Compared with an established protocol for lysis and DNA purification using the commercial kit GeneReleaserTM (Bioventures) (GRL method), the novel SW-EL method provided higher DNA yields. With the addition of GeneReleaser to the PCR reaction to function as a chelating resin, rpoB genes (serving as model genes) could be successfully amplified. The SW-EL method has potential to be of use for DNA-based analysis of microbial consortia present in heavy-oil contaminated soils.