Malaria poses a great challenge for the maintenance of good public health and sustenance of human wellbeing in many parts of the world. Apparently, the anthropogenic global warming has expanded the spatio-temporal extent of the disease; incidences are now reported beyond tropics and in non-endemic seasons. This emerging trend of climate change has increased the malaria risk factor for millions more across the globe. While global warming remains a key factor to address the future adaptations and mitigation measures, the existing association between climate and malaria prevalence needs careful observations and analyses besides the non-climatic factors. Such a climate association is investigated here with the available malaria case counts in the northeastern districts of South Africa. It is found that the regional variations in seasonal rainfall and temperature, that primarily control mosquito population and thereby infection rates, are linked with a basin-scale climate phenomenon manifested as a dipole pattern in the interannual anomalies of sea surface temperature (SST) of southwestern Indian Ocean. In addition to the year-to-year variations, partly related to the basin warming, a decadal shift in the SST dipole pattern, and associated decrease in seasonal rainfall, leads to decreasing number of case counts in recent years as indicated by the malaria records.