Carbon monoxide (CO) is commonly known as a toxic gas, yet both cultivation studies and emerging genome sequences of bacteria and archaea establish that CO is a widely utilized microbial growth substrate. In this study, we determined the prevalence of anaerobic carbon monoxide dehydrogenases ([Ni,Fe]-CODHs) in currently available genomic sequence databases. Currently, 185 out of 2887, or 6% of sequenced bacterial and archaeal genomes possess at least one gene encoding [Ni,Fe]-CODH, the key enzyme for anaerobic CO utilization. Many genomes encode multiple copies of [Ni,Fe]-CODH genes whose functions and regulation are correlated with their associated gene clusters. The phylogenetic analysis of this extended protein family revealed six distinct clades; many clades consisted of [Ni,Fe]-CODHs that were encoded by microbes from disparate phylogenetic lineages, based on 16S rRNA sequences, and widely ranging physiology. To more clearly define if the branching patterns observed in the [Ni,Fe]-CODH trees are due to functional conservation vs. evolutionary lineage, the genomic context of the [Ni,Fe]-CODH gene clusters was examined, and superimposed on the phylogenetic trees. On the whole, there was a correlation between genomic contexts and the tree topology, but several functionally similar [Ni,Fe]-CODHs were found in different clades. In addition, some distantly related organisms have similar [Ni,Fe]-CODH genes. Thermosinus carboxydivorans was used to observe horizontal gene transfer (HGT) of [Ni,Fe]-CODH gene clusters by applying Kullback-Leibler divergence analysis methods. Divergent tetranucleotide frequency and codon usage showed that the gene cluster of T. carboxydivorans that encodes a [Ni,Fe]-CODH and an energy-converting hydrogenase is dissimilar to its whole genome but is similar to the genome of the phylogenetically distant Firmicute, Carboxydothermus hydrogenoformans. These results imply that T carboxydivorans acquired this gene cluster via HGT from a relative of C. hydrogenoformans.