Millions of individuals are at risk of malaria infection in sub-Saharan Africa. Compared to other highly affected countries on the continent, South Africa has an excellent record of malaria control. Nevertheless, the northeastern districts of the country, neighboring some of the worst malaria affected regions in southern Africa, still experience seasonal malaria outbreaks particularly during the summer months of September-February. The year to year variations of the malaria outbreaks in southern Africa, as in many other parts of the world, are often linked to interannual variations in rainfall and temperature. These meteorological factors in turn are seen to be associated with large-scale climate phenomena such as El Niño/La Niña. Here, we present evidence of a new mode of climate variation in the Indian Ocean that could explain the interannual variation of malaria incidences in South Africa. This phenomenon appeared as a dipolar association in the sea surface temperature (SST) anomalies of southwestern Indian Ocean. Both poles of the dipole strongly correlated with the malaria incidence index of Vhembe district, one of South Africa's highest malaria-affected districts. The identified correlations were stronger than those found with other climate phenomena such as El Niño/La Niña and Indian Ocean Dipole. A decadal shift in the SST dipole pattern was also observed, and the associated decrease in seasonal rainfall could partly explain the recent reduction in malaria cases.