In nature, organisms are simultaneously exposed to multiple stresses (i.e. complex environments) that often fluctuate unpredictably. Although both these factors have been studied in isolation, the interaction of the two remains poorly explored. To address this issue, we selected laboratory populations of Escherichia coli under complex (i.e. stressful combinations of pH, H2O2 and NaCl) unpredictably fluctuating environments for ~900 generations. We compared the growth rates and the corresponding trade-off patterns of these populations to those that were selected under constant values of the component stresses (i.e. pH, H2O2 and NaCl) for the same duration. The fluctuation-selected populations had greater mean growth rate and lower variation for growth rate over all the selection environments experienced. However, whereas the populations selected under constant stresses experienced trade-offs in the environments other than those in which they were selected, the fluctuation-selected populations could bypass the across-environment trade-offs almost entirely. Interestingly, trade-offs were found between growth rates and carrying capacities. The results suggest that complexity and fluctuations can strongly affect the underlying trade-off structure in evolving populations.