Abstract Drug combinations are a promising strategy to counter antibiotic resistance. However, current experimental and computational approaches do not account for the entire complexity involved in combination therapy design, such as the effect of pathogen metabolic heterogeneity, changes in the growth environment, drug treatment order, and time interval. To address these limitations, we present a comprehensive approach that uses genome-scale metabolic modeling and machine learning to guide combination therapy design. Our mechanistic approach (a) accommodates diverse data types, (b) accounts for time- and order-specific interactions, and (c) accurately predicts drug interactions in various growth conditions and their robustness to pathogen metabolic heterogeneity. Our approach achieved high accuracy (area under the receiver operating curve (AUROC) = 0.83 for synergy, AUROC = 0.98 for antagonism) in predicting drug interactions for Escherichia coli cultured in 57 metabolic conditions based on experimental validation. The entropy in bacterial metabolic response was predictive of combination therapy outcomes across time scales and growth conditions. Simulation of metabolic heterogeneity using population FBA identified two subpopulations of E. coli cells defined by the levels of three proteins (eno, fadB, and fabD) in glycolysis and lipid metabolism that influence cell tolerance to a broad range of antibiotic combinations. Analysis of the vast landscape of condition-specific drug interactions revealed a set of 24 robustly synergistic drug combinations with potential for clinical use.