Evidence suggests that novel enzyme functions evolved from low-level promiscuous activities in ancestral enzymes. Yet, the evolutionary dynamics and physiological mechanisms of how such side activities contribute to systems-level adaptations are poorly understood. Furthermore, it remains untested whether knowledge of an organisms promiscuous reaction set ( underground metabolism) can aid in forecasting the genetic basis of metabolic adaptations. Here, we employ a computational model of underground metabolism and laboratory evolution experiments to examine the role of enzyme promiscuity in the acquisition and optimization of growth on predicted non-native substrates in E. coli K-12 MG1655. After as few as 20 generations, the evolving populations repeatedly acquired the capacity to grow on five predicted novel substrates-D-lyxose, D-2-deoxyribose, D-arabinose, m-tartrate, and monomethyl succinate-none of which could support growth in wild-type cells. Promiscuous enzyme activities played key roles in multiple phases of adaptation. Altered promiscuous activities not only established novel high-efficiency pathways, but also suppressed undesirable metabolic routes. Further, structural mutations shifted enzyme substrate turnover rates towards the new substrate while retaining a preference for the primary substrate. Finally, genes underlying the phenotypic innovations were accurately predicted by genome-scale model simulations of metabolism with enzyme promiscuity. Computational approaches will be essential to synthesize the complex role of promiscuous activities in applied biotechnology and in models of evolutionary adaptation.