Malaria resurgence in African highlands in the 1990s has raised questions about the underlying drivers of the increase in disease incidence including the role of El-Niño-Southern Oscillation (ENSO). However, climatic anomalies other than the ENSO are clearly associated with malaria outbreaks in the highlands. Here we show that the Indian Ocean Dipole (IOD), a coupled ocean-atmosphere interaction in the Indian Ocean, affected highland malaria re-emergence. Using cross-wavelet coherence analysis, we found four-year long coherent cycles between the malaria time series and the dipole mode index (DMI) in the 1990s in three highland localities. Conversely, we found a less pronounced coherence between malaria and DMI in lowland localities. The highland/lowland contrast can be explained by the effects of mesoscale systems generated by Lake Victoria on its climate basin. Our results support the need to consider IOD as a driving force in the resurgence of malaria in the East African highlands.