Background The impact of historical contingency, i.e. the past evolutionary history of a population, on further adaptation is mostly unknown at both the phenotypic and genomic levels. We addressed this question using a two-step evolution experiment. First, replicate populations of Escherichia coli were propagated in four different environmental conditions for 1000 generations. Then, all replicate populations were transferred and propagated for further 1000 generations to a single new environment. Results Using this two-step experimental evolution strategy, we investigated, at both the phenotypic and genomic levels, whether and how adaptation in the initial historical environments impacted evolutionary trajectories in a new environment. We showed that both the growth rate and fitness of the evolved populations obtained after the second step of evolution were contingent upon past evolutionary history. In contrast however, the genes that were modified during the second step of evolution were independent from the previous history of the populations. Conclusions Our work suggests that historical contingency affects phenotypic adaptation to a new environment. This was however not reflected at the genomic level implying complex relationships between environmental factors and the genotype-to-phenotype map.