The causes of the recent re-emergence of malaria in the East African highlands probably involve a complex interplay among multiple factors, including climate, land use, topography, inadequate use of antimalarial drugs and drug resistance, socioeconomic status, health policy and public health control measures. It is important to determine the relative contribution of these factors. In our study, we statistically attributed the effects of autocorrelation, seasonality and climate variability to the temporal variation in the number of malaria patients in several highland sites in East Africa. We found that in three out of seven sites, climate variability contributed more variance to malaria patient numbers than did autocorrelation and seasonality. In all seven study sites, we found highly significant nonlinear, synergistic effects of the interaction between rainfall and temperature on malaria patient time series.