Bacteria frequently lose biosynthetic genes, thus making them dependent on an environmental uptake of the corresponding metabolite. Despite the ubiquity of this 'genome streamlining', it is generally unclear whether the concomitant loss of biosynthetic functions is favored by natural selection or rather caused by random genetic drift. Here we demonstrate experimentally that a loss of metabolic functions is strongly selected for when the corresponding metabolites can be derived from the environment. Serially propagating replicate populations of the bacterium Escherichia coli in amino acid-containing environments revealed that auxotrophic genotypes rapidly evolved in less than 2,000 generations in almost all replicate populations. Moreover, auxotrophs also evolved in environments lacking amino acids - yet to a much lesser extent. Loss of these biosynthetic functions was due to mutations in both structural and regulatory genes. In competition experiments performed in the presence of amino acids, auxotrophic mutants gained a significant fitness advantage over the evolutionary ancestor, suggesting their emergence was selectively favored. Interestingly, auxotrophic mutants derived amino acids not only via an environmental uptake, but also by cross-feeding from coexisting strains. Our results show that adaptive fitness benefits can favor biosynthetic loss-of-function mutants and drive the establishment of intricate metabolic interactions within microbial communities.