Adaptive laboratory evolution has proven highly effective for obtaining microorganisms with enhanced capabilities. Yet, this method is inherently restricted to the traits that are positively linked to cell fitness, such as nutrient utilization. Here, we introduce coevolution of obligatory mutualistic communities for improving secretion of fitness-costly metabolites through natural selection. In this strategy, metabolic cross-feeding connects secretion of the target metabolite, despite its cost to the secretor, to the survival and proliferation of the entire community. We thus co-evolved wild-type lactic acid bacteria and engineered auxotrophic Saccharomyces cerevisiae in a synthetic growth medium leading to bacterial isolates with enhanced secretion of two B-group vitamins, viz., riboflavin and folate. The increased production was specific to the targeted vitamin, and evident also in milk, a more complex nutrient environment that naturally contains vitamins. Genomic, proteomic and metabolomic analyses of the evolved lactic acid bacteria, in combination with flux balance analysis, showed altered metabolic regulation towards increased supply of the vitamin precursors. Together, our findings demonstrate how microbial metabolism adapts to mutualistic lifestyle through enhanced metabolite exchange.