The long-term patterns of malaria in the East African highlands typically involve not only a general upward trend in cases but also a dramatic increase in the size of epidemic outbreaks. The role of climate variability in driving epidemic cycles at interannual time scales remains controversial, in part because it has been seen as conflicting with the alternative explanation of purely endogenous cycles exclusively generated by the nonlinear dynamics of the disease. We analyse a long temporal record of monthly cases from 1970 to 2003 in a highland of western Kenya with both a time-series epidemiological model (time-series susceptible-infected-recovered) and a statistical approach specifically developed for non-stationary patterns. Results show that multiyear cycles of malaria outbreaks appear in the 1980s, concomitant with the timing of a regime shift in the dynamics of cases; the cycles become more pronounced in the 1990s, when the coupling between disease and rainfall is also stronger as the variance of rainfall increased at the frequencies of coupling. Disease dynamics and climate forcing play complementary and interacting roles at different temporal scales. Thus, these mechanisms should not be viewed as alternative and their interaction needs to be integrated in the development of future predictive models.