In a study aiming to assess bacterial evolution in complex growth media, we evaluated the long-term adaptive response of Escherichia coli MC1000 in Luria-Bertani (LB) medium. Seven parallel populations were founded and followed over 150 days in sequential batch cultures under three different oxygen conditions (defined environments), and 19 evolved forms were isolated. The emergence of forms with enhanced fitness was evident in competition experiments of all evolved forms versus the ancestral strain. The evolved forms were then subjected to phenotypic and genomic analyses relative to the ancestor. Profound changes were found in their phenotypes as well as whole-genome sequences. Interestingly, considerable heterogeneity was found at the intrapopulational level. However, consistently occurring parallel adaptive responses were found across all populations. The evolved forms all contained a mutation in galR, a repressor of the galactose operon. Concomitantly, the new forms revealed enhanced growth on galactose as well as galactose-containing disaccharides. This response was likely driven by the LB medium.