Tolerance to high product concentrations is a major barrier to achieving economically viable processes for bio-based chemical production. Chemical tolerance mechanisms are often unknown, thus their rational design is not achievable. To reveal unknown tolerance mechanisms we used an automated platform to evolve Escherichia coli to grow in previously toxic concentrations of 11 chemicals that have applications as polymer precursors, chemical intermediates, or biofuels. Re-sequencing of isolates from 88 independently evolved populations, reconstruction of mutations, and cross-compound tolerance profiling was employed to uncover general and specific tolerance mechanisms. We found that: 1) the broad tolerance of strains towards chemicals varied significantly depending on the chemical stress condition under which the strain was evolved; 2) the strains that acquired high levels of NaCl tolerance also became broadly tolerant to most chemicals; 3) genetic tolerance mechanisms included alterations in regulatory, cell wall, transcriptional and translational functions, as well as more chemical-specific mechanisms related to transport and metabolism; 4) using pre-tolerized starting strains can significantly enhance subsequent production of chemicals when a production pathway is inserted; and 5) only a subset of the evolved isolates showed improved production indicating that this approach is especially useful when a large number of independently evolved isolates are screened for production. We provide a comprehensive genotype-phenotype map based on identified mutations and growth phenotypes for 224 chemical tolerant strains.