It has recently become feasible to study the basis and nature of evolutionary changes in bacteria in an experimental setting using defined media. However, assessment of adaptive changes in complex environments has been scarce. In an effort to describe the responses in such environments, we unravel, in a comparative approach, the transcriptional and genetic profiles of 19 Escherichia coli strains that evolved in Luria Bertani medium under three different oxygen regimes over 1000 generations. A positive relationship between upregulation of gene expression and the number of mutations was observed, suggesting that a number of metabolic pathways were activated. Phenotypic polymorphisms were observed in parallel cultures, of which some were related with mutations at the regulatory level. Non-parallel responses were observed at the intrapopulational level, which is indicative of diversifying selection. Parallel responses encompassed transcriptome diversity, and their effects were directly affected by differing genomic backgrounds. A fluctuating selective force produced higher phenotypic diversity compared with constant forces. This study demonstrates how phenotypic innovations may depend on the relationship between genomic changes and local ecological conditions. Using both comparative genomics and transcriptomics approaches, the results help elucidating various adaptive responses in cultures in unexplored complex environments.