Microbial populations founded by a single clone and propagated under resource limitation can become polymorphic. We sought to elucidate genetic mechanisms whereby a polymorphism evolved in Escherichia coli under glucose limitation and persisted because of cross-feeding among multiple adaptive clones. Apart from a 29 kb deletion in the dominant clone, no large-scale genomic changes distinguished evolved clones from their common ancestor. Using transcriptional profiling on co-evolved clones cultured separately under glucose-limitation we identified 180 genes significantly altered in expression relative to the common ancestor grown under similar conditions. Ninety of these were similarly expressed in all clones, and many of the genes affected (e.g., mglBAC, mglD, and lamB) are in operons coordinately regulated by CRP and/or rpoS. While the remaining significant expression differences were clone-specific, 93% were exhibited by the majority clone, many of which are controlled by global regulators, CRP and CpxR. When transcriptional profiling was performed on adaptive clones cultured together, many expression differences that distinguished the majority clone cultured in isolation were absent, suggesting that CpxR may be activated by overflow metabolites removed by cross-feeding strains in co-culture. Relative to their common ancestor, shared expression differences among adaptive clones were partly attributable to early-arising shared mutations in the trans-acting global regulator, rpoS, and the cis-acting regulator, mglO. Gene expression differences that distinguished clones may in part be explained by mutations in trans-acting regulators malT and glpK, and in cis-acting sequences of acs. In the founder, a cis-regulatory mutation in acs (acetyl CoA synthetase) and a structural mutation in glpR (glycerol-3-phosphate repressor) likely favored evolution of specialists that thrive on overflow metabolites. Later-arising mutations that led to specialization emphasize the importance of compensatory rather than gain-of-function mutations in this system. Taken together, these findings underscore the importance of regulatory change, founder genotype, and the biotic environment in the adaptive evolution of microbes.