Cobalamin in the form of adenosylcobalamin (Ado-CBL) is known to repress expression of genes for vitamin B12 biosynthesis and be transported by a posttranscriptional regulatory mechanism, which involves direct binding of Ado-CBL to 5_untranslated gene regions (5_UTR). Using comparative analysis of genes and regulatory regions, we identified a highly conserved RNA structure, the B12-element, which is widely distributed in 5_UTRs of vitamin B12-related genes in eubacteria. Multiple alignment of approximately 200 B12-elements from 66 bacterial genomes reveals their common secondary structure and several extended regions of sequence conservation, including the previously known B12-box motif. In analogy to the model of regulation of the riboflavin and thiamin biosynthesis, we suggest Ado-CBL-mediated regulation based on formation of alternative RNA structures including the B12-element. In Gram-negative proteobacteria, as well as in cyanobacteria, actinobacteria, and the CFB group, the cobalamin biosynthesis and vitamin B12 transport genes are predicted to be regulated by inhibition of translation initiation, whereas in the Bacillus/Clostridium group of Gram-positive bacteria, these genes seem to be regulated by transcriptional antitermination. Phylogenetic analysis of the B12-elements reveals a large number of likely duplications of B12-elements in several bacterial genomes. These lineage-specific duplications of RNA regulatory elements seem to be a major evolutionary mechanism for expansion of the vitamin B12 regulon.