BACKGROUND: Nearly half of the world's population (3.2 billion people) were at risk of malaria in 2015, and resistance to current therapies is a major concern. While the standard of care includes drug combinations, there is a pressing need to identify new combinations that can bypass current resistance mechanisms. In the work presented here, a combined transcriptional drug repositioning/discovery and machine learning approach is proposed. METHODS: The integrated approach utilizes gene expression data from patient-derived samples, in combination with large-scale anti-malarial combination screening data, to predict synergistic compound combinations for three Plasmodium falciparum strains (3D7, DD2 and HB3). Both single compounds and combinations predicted to be active were prospectively tested in experiment. RESULTS: One of the predicted single agents, apicidin, was active with the AC50 values of 74.9, 84.1 and 74.9 nM in 3D7, DD2 and HB3 P. falciparum strains while its maximal safe plasma concentration in human is 547.6 ± 136.6 nM. Apicidin at the safe dose of 500 nM kills on average 97% of the parasite. The synergy prediction algorithm exhibited overall precision and recall of 83.5 and 65.1% for mild-to-strong, 48.8 and 75.5% for moderate-to-strong and 12.0 and 62.7% for strong synergies. Some of the prospectively predicted combinations, such as tacrolimus-hydroxyzine and raloxifene-thioridazine, exhibited significant synergy across the three P. falciparum strains included in the study. CONCLUSIONS: Systematic approaches can play an important role in accelerating discovering novel combinational therapies for malaria as it enables selecting novel synergistic compound pairs in a more informed and cost-effective manner.