There is considerable understanding about how laboratory populations respond to predictable (constant or deteriorating environment) selection for single environmental variables such as temperature or pH. However, such insights may not apply when selection environments comprise multiple variables that fluctuate unpredictably, as is common in nature. To address this issue, we grew replicate laboratory populations of Escherichia coli in nutrient broth whose pH and concentrations of salt (NaCl) and hydrogen peroxide (H2O2) were randomly changed daily. After ~170 generations, the fitness of the selected populations had not increased in any of the three selection environments. However, these selected populations had significantly greater fitness in four novel environments which have no known fitness-correlation with tolerance to pH, NaCl or H2O2. Interestingly, contrary to expectations, hypermutators did not evolve. Instead, the selected populations evolved an increased ability for energy-dependent efflux activity that might enable them to throw out toxins, including antibiotics, from the cell at a faster rate. This provides an alternate mechanism for how evolvability can evolve in bacteria and potentially lead to broad-spectrum antibiotic resistance, even in the absence of prior antibiotic exposure. Given that environmental variability is increasing in nature, this might have serious consequences for public health.