The cobalt-containing cobamides such as vitamin B₁₂ are the most complicated non-polymer biomolecules in nature that have essential biochemical functions in all domains of life. In organohalide respiration, a vital process for the global cycling of natural and anthropogenic organohalogens, cobamides are the requisite prosthetic groups for the carbon-halogen bond-cleaving reductive dehalogenases. Organohalide-respiring bacteria such as Sulfurospirrilium multivorans (Smul) and Dehalococcoides mccartyi (Dhc) are key players involved in the complete detoxification of tetrachloroethene (PCE) and trichloroethene (TCE) to environmentally benign ethene. While Smul is able to synthesize an unusual Nor-type of cobamide to sustain PCE-dechlorination activity, the genome sequence analysis demonstrated that Dhc strains are corrinoid auxotrophs and lack the ability for de novo biosynthesis of corrinoid, therefore, exogenous corrinoid (i.e., vitamin B₁₂) must be available to enable and sustain Dhc reductive dechlorination activity. We re-assembled the cobalt-transport and corrinoid-metabolism pathways in sequenced Dhc genome and demonstrated the strategies that Dhc strain employ to rescue their corrinoid auxotrophy in pure cultures and defined co-cultures. Understanding the bottlenecks limiting the activity of cobalt-dependent organohalide-respiring bacteria will not only elucidate microbial ecology in the subsurface environments, but also may lead to innovative engineering approaches that enhance reductive dechlorination rates and extents and enable more efficient bioremediation applications.