A pleiotropic mutant of Paracoccus denitrificans, which has a severe defect that affects its anaerobic growth when either nitrate, nitrite, or nitrous oxide is used as the terminal electron acceptor and which is also unable to use ethanolamine as a carbon and energy source for aerobic growth, was isolated. This phenotype of the mutant is expressed only during growth on minimal media and can be reversed by addition of cobalamin (vitamin B₁₂) or cobinamide to the media or by growth on rich media. Sequence analysis revealed the mutation causing this phenotype to be in a gene homologous to cobK of Pseudomonas denitrificans, which encodes precorrin-6x reductase of the cobalamin biosynthesis pathway. Convergently transcribed with cobK is a gene homologous to cobJ of Pseudomonas denitrificans, which encodes precorrin-3b methyltransferase. The inability of the cobalamin auxotroph to grow aerobically on ethanolamine implies that wild-type P. denitrificans (which can grow on ethanolamine) expresses a cobalamin-dependent ethanolamine ammonia lyase and that this organism synthesizes cobalamin under both aerobic and anaerobic growth conditions. Comparison of the cobK and cobJ genes with their orthologues suggests that P. denitrificans uses the aerobic pathway for cobalamin synthesis. It is paradoxical that under anaerobic growth conditions, P. denitrificans appears to use the aerobic (oxygen-requiring) pathway for cobalamin synthesis. Anaerobic growth of the cobalamin auxotroph could be restored by the addition of deoxyribonucleosides to minimal media. These observations provide evidence that P. denitrificans expresses a cobalamin-dependent ribonucleotide reductase, which is essential for growth only under anaerobic conditions.