We investigated the relationship between genomic and phenotypic evolution among replicate populations of Escherichia coli evolved for 1000 generations in four different environments. By resequencing evolved genomes, we identified parallel changes in genes encoding transcription regulators within and between environments. Depending on both the environment and the altered gene, genetic parallelism at the gene level involved mutations that affected identical codons, protein domains or were widely distributed across the gene. Evolved clones were characterized by parallel phenotypic changes in their respective evolution environments but also in the three alternative environments. Phenotypic parallelism was high for clones that evolved in the same environment, even in the absence of genetic parallelism. By contrast, clones that evolved in different environments revealed a higher parallelism in correlated responses when they shared mutated genes. Altogether, this work shows that after an environmental change or the colonization of a new habitat, similar ecological performance might be expected from individuals that share mutated genes or that experienced similar past selective pressures.