Organohalide-respiring Bacteria (OHRB) play key roles in the reductive dehalogenation of natural organohalides and anthropogenic chlorinated contaminants. Reductive dehalogenases (RDases) catalyze the cleavage of carbon-halogen bonds, enabling respiratory energy conservation and growth. Large numbers of RDase genes, a majority lacking experimental characterization of function, are found on the genomes of OHRB. In silico genomics tools were employed to identify shared sequence features among RDase genes and proteins, predict RDase functionality, and elucidate RDase evolutionary history. These analyses showed that the RDase superfamily could be divided into proteins exported to the membrane and cytoplasmic proteins, indicating that not all RDases function in respiration. Further, Hidden Markov models (HMMs) and multiple sequence alignments (MSAs) based upon biochemically characterized RDases identified previously uncharacterized members of an RDase superfamily, delineated protein domains and amino acid motifs serving to distinguish RDases from unrelated iron-sulfur proteins. Such conserved and discriminatory features among RDases may facilitate monitoring of organohalide-degrading microbial communities or improve accuracy of genome annotation. Phylogenetic analyses of RDase superfamily sequences provided evidence of convergent evolution and horizontal gene transfer (HGT) across distinct OHRB genera. Yet, the low frequency of RDase transfer outside the genus level and the absence of RDase transfer between phyla indicate that RDases evolve primarily by vertical evolution or HGT is restricted among related OHRB strains. Polyphyletic evolutionary lineages within the RDase superfamily comprise distantly-related RDases, some exhibiting activities towards the same substrates, suggesting a longstanding history of OHRB adaptation to natural organohalides. Similar functional and phylogenetic analyses provided evidence that nitrous oxide (N₂O, a potent greenhouse gas) reductase (nosZ) genes from versatile OHRB members of the Anaeromyxobacter and Desulfomonile genera comprised a nosZ sub-family evolutionarily distinct from nosZ found in non-OHRB denitrifiers. Hence, elucidation of RDase and NosZ sequence diversity may enhance the mitigation of anthropogenic organohalides and greenhouse gases (i.e., N₂O), respectively. The tetrachloroethene-respiring bacterium Geobacter lovleyi strain SZ exhibited genomic features distinguishing it from non-organohalide-respiring members of the Geobacter genus, including a conjugative pilus transfer gene cluster, a chromosomal genomic island harboring two RDase genes, and a diminished set of c-type cytochrome genes. The G. lovleyi strain SZ genome also harbored a 77 kbp plasmid carrying 15 out of the 24 genes involved in biosynthesis of corrinoid, likely related to this strains ability to degrade PCE to cis-DCE in the absence of supplied corrinoid (i.e., vitamin B₁₂). Although corrinoids are essential cofactors to RDases, the strictly organohalide-respiring Dehalococcoides mccartyi strains are corrinoid auxotrophs and depend upon uptake of extracellular corrinoids via Archaeal and Bacterial salvage pathways. A key corrinoid salvage gene in D. mccartyi, cbiZ, occurs at duplicated loci adjacent to RDase genes and appears to have been horizontally-acquired from Archaea. These comparative genome analyses highlight RDase dependencies upon corrinoids and also suggest mobile genomic elements (e.g., plasmids) are associated with organohalide respiration and corrinoid acquisition among OHRB. In summary, analyses of OHRB genomes promise to enable more complete modeling of metabolic and evolutionary processes associated with the turnover of organohalides in anoxic environments. These efforts also expand knowledge of biomarkers for monitoring OHRB activity in anoxic environments, and will improve our understanding of the fate of chlorinated contaminants.