Recent experiments show that adaptive Darwinian evolution in one environment can lead to the emergence of multiple new traits that provide no immediate benefit in this environment. Such latent non-adaptive traits, however, can become adaptive in future environments. We do not know whether mutation or environment-driven selection is more important for the emergence of such traits. To find out, we evolve multiple wild-type and mutator E. coli populations under two mutation rates in simple (single antibiotic) environments and in complex (multi-antibiotic) environments. We then assay the viability of evolved populations in dozens of new environments and show that all populations become viable in multiple new environments different from those they had evolved in. The number of these new environments increases with environmental complexity but not with the mutation rate. Genome sequencing demonstrates the reason: Different environments affect pleiotropic mutations differently. Our experiments show that the selection pressure provided by an environment can be more important for the evolution of novel traits than the mutational supply experienced by a wild-type and a mutator strain of E. coli.