Combination antibiotic therapies are clinically important in the fight against bacterial infections. However, the search space of drug combinations is large, making the identification of effective combinations a challenging task. Here, we present a computational framework that uses substructure profiles derived from the molecular structures of drugs and predicts antibiotic interactions. Using a previously published data set of 153 drug pairs, we showed that substructure profiles are useful in predicting synergy. We experimentally measured the interaction of 123 new drug pairs, as a prospective validation set for our approach, and identified 37 new synergistic pairs. Of the 12 pairs predicted to be synergistic, 10 were experimentally validated, corresponding to a 2.8-fold enrichment. Having thus validated our methodology, we produced a compendium of interaction predictions for all pairwise combinations among 100 antibiotics. Our methodology can make reliable antibiotic interaction predictions for any antibiotic pair within the applicability domain of the model since it solely requires chemical structures as an input.