Cobalamin (vitamin B12 ) is a cofactor for essential metabolic reactions in multiple eukaryotic taxa, including major primary producers such as algae, and yet only prokaryotes can produce it. Many bacteria can colonize the algal phycosphere, forming stable communities that gain preferential access to photosynthate and in return provide compounds such as B12 . Extended coexistence can then drive gene loss, leading to greater algal-bacterial interdependence. In this study, we investigate how a recently evolved B12 -dependent strain of Chlamydomonas reinhardtii, metE7, forms a mutualism with certain bacteria, including the rhizobium Mesorhizobium loti and even a strain of the gut bacterium E. coli engineered to produce cobalamin. Although metE7 was supported by B12 producers, its growth in co-culture was slower than the B12 -independent wild-type, suggesting that high bacterial B12 provision may be necessary to favour B12 auxotrophs and their evolution. Moreover, we found that an E. coli strain that releases more B12 makes a better mutualistic partner, and although this trait may be more costly in isolation, greater B12 release provided an advantage in co-cultures. We hypothesize that, given the right conditions, bacteria that release more B12 may be selected for, particularly if they form close interactions with B12 -dependent algae.