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 not well characterized. Furthermore, it remains untested whether knowledge of an organism's promiscuous reaction set, or 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 Escherichia coli K-12 MG1655. After as few as approximately 20 generations, evolved populations repeatedly acquired the capacity to grow on five predicted non-native substrates-D-lyxose, D-2-deoxyribose, D-arabinose, m-tartrate, and monomethyl succinate. Altered promiscuous activities were shown to be directly involved in establishing high-efficiency pathways. Structural mutations shifted enzyme substrate turnover rates toward 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.