Microbes exhibit short and long term responses when exposed to challenging environmental conditions. To what extent these responses are correlated, what their evolutionary potential is and how they translate to cross-stress fitness is still unclear. In this study, we comprehensively characterized the response of Escherichia coli populations to four abiotic stresses (n-butanol, osmotic, acidic, and oxidative) and their combinations by performing genome-scale transcriptional analysis and growth profiling. We performed an analysis of their cross-stress behavior which identified 15 cases of cross- protection and one case of cross vulnerability. To elucidate the evolutionary potential of stress responses to individual stresses and stress combinations, we re-sequenced E. coli populations evolved in those four environments for 500 generations. We developed and applied a network-driven method that integrates mutations and differential expression to identify core and stress-specific gene communities that are likely to have a phenotypic impact. Our results suggest that beyond what is expected from the general stress response mechanisms, cross-stress behavior arises both from common pathways, several including metal ion binding and glycolysis/gluconeogenesis, and stress-specific expression programs. The stress-specific dependences uncovered, argue that cross-stress behavior is ubiquitous and central to understanding microbial physiology under stressful conditions.