Vitamin B12 (cobalamin) is a dietary requirement for humans because it is an essential cofactor for two enzymes, methylmalonyl-CoA mutase and methionine synthase (METH). Land plants and fungi neither synthesize or require cobalamin because they do not contain methylmalonyl-CoA mutase, and have an alternative B12-independent methionine synthase (METE). Within the algal kingdom, approximately half of all microalgal species need the vitamin as a growth supplement, but there is no phylogenetic relationship between these species, suggesting that the auxotrophy arose multiple times through evolution. We set out to determine the underlying cellular mechanisms for this observation by investigating elements of B12 metabolism in the sequenced genomes of 15 different algal species, with representatives of the red, green, and brown algae, diatoms, and coccolithophores, including both macro- and microalgae, and from marine and freshwater environments. From this analysis, together with growth assays, we found a strong correlation between the absence of a functional METE gene and B12 auxotrophy. The presence of a METE unitary pseudogene in the B12-dependent green algae Volvox carteri and Gonium pectorale, relatives of the B12-independent Chlamydomonas reinhardtii, suggest that B12 dependence evolved recently in these lineages. In both C. reinhardtii and the diatom Phaeodactylum tricornutum, growth in the presence of cobalamin leads to repression of METE transcription, providing a mechanism for gene loss. Thus varying environmental conditions are likely to have been the reason for the multiple independent origins of B12 auxotrophy in these organisms. Because the ultimate source of cobalamin is from prokaryotes, the selective loss of METE in different algal lineages will have had important physiological and ecological consequences for these organisms in terms of their dependence on bacteria.