Adenosylcobalamin (Coenzyme B12, AdoCbl) is a cofactor that is essential for organisms in all three domains of life, but is only synthesized by bacteria and archaea. While much is known about the biosynthesis of AdoCbl, many gaps remain. There is a separate aerobic and anaerobic pathway for the synthesis of the corrinoid ring of AdoCbl. These pathways involve a different set of enzymes and exist separately in different prokaryotic organisms. The pathways converge with the late steps where homologous enzymes carry out several, but not all steps. The late steps of the anaerobic pathway has been well studies in Salmonella enterica sv Typhimurium LT2. Homologous enzymes have not been identified for some of the late steps of the aerobic pathway, or within archaea or hyperthermophiles, which use the anaerobic pathway. Among these yet-to-be identified enzymes are the Adenosylcobalamin-5-phosphate phosphatase (EC 3.1.3.73) (CobC in S. Typhimurium, CobZ in archaea), which catalyze the final step, and the L-threonine kinase (EC 2.7.1.177) (PduX in S. Typhimurium), which catalyzes the first step in the synthesis of the 1-amino-2-propanol-O-2-phosphate (AP-P) nucleotide linker moiety of AdoCbl. Here we identify an enzyme named BluE, a L-threonine (L-Thr) kinase in Rhodobacter sphaeroides, an organism that synthesizes AdoCbl via the aerobic pathway. We show that RsBluE has L-Thr kinase activity in vitro and complements a S. Typhimurium pduX strain in vivo. Phylogenic analysis of bluE shows it is restricted to a few Rhodobacterales that have a strict requirement for the cobalamin with 5,6-dimethylbenzimidazole as the lower ligand and AP-P as the nucleotide linker. To date no archaeal genomes have been found to encode pduX or bluE homologues. Investigations of the unusual archaeal L-threonine-O-3-phosphate (L-Thr-P) decarboxylase (CobD, EC 4.1.1.81) from Methanosarcina mazei revealed that this enzyme is bifunctional, conferring L-Thr kinase activity in addition to the expected L-Thr-P decarboxylation. MmCobD has a [4Fe-4S]2+ cluster domain that appears to have a regulatory function for both enzymatic activities. Bioinformatics analyses suggest that many organisms that lack pduX or bluE homologues encode a CobD with a slightly longer N-terminus similar to that of MmCobD. This region might encode all or part of a motif for the L-Thr kinase activity.