Polychlorinated dibenzo-p-dioxin (PCDD)-contaminated sites are widespread and associated with a variety of anthropogenic sources. PCDDs and other organohalide pollutants can serve as terminal electron acceptors for anaerobic respiration by specialized bacteria containing reductive dehalogenases (RdhA). These microorganisms, therefore, play an important role in the bioremediation of PCDD-contaminated sites. Two anaerobic enrichment cultures established using sediments collected from the PCDD-polluted Hackensack (USA) and Kymijoki (Finland) rivers showed robust reductive dechlorination of 1,2,3,4-tetrachlorodibenzo-p-dioxin (1,2,3,4-TeCDD). Here, we report on the draft genome reconstructions of the two predominant Dehalococcoides strains from the metagenomes of these dehalogenating enrichment cultures. Furthermore, we gathered a complete list of RdhA in the two predominant Dehalococcoides strains, and determined which are likely to be responsible for the reductive dechlorination of PCDDs. The divergent rdhA gene profiles of the Dehalococcoides strains likely reflect their exposure to different organohalide compounds in their original habitats. Both draft genomes contained a full length rdhA gene with high sequence similarity to a rdhA gene, i.e. cbrA, found in Dehalococcoides mccartyi CBDB1 known to reductively dechlorinate 1,2,3,4-tetrachlorobenzene. This gene homologue might also be responsible for reductive dechlorination of 1,2,3,4-TeCDD in the enrichments and could be used as a biomarker to determine the potential for the bioremediation of PCDD-contaminated sediments.