Climate change impacts on malaria are typically assessed with scenarios for the long-term future. Here we focus instead on the recent past (1970-2003) to address whether warmer temperatures have already increased the incidence of malaria in a highland region of East Africa. Our analyses rely on a new coupled mosquito-human model of malaria, which we use to compare projected disease levels with and without the observed temperature trend. Predicted malaria cases exhibit a highly nonlinear response to warming, with a significant increase from the 1970s to the 1990s, although typical epidemic sizes are below those observed. These findings suggest that climate change has already played an important role in the exacerbation of malaria in this region. As the observed changes in malaria are even larger than those predicted by our model, other factors previously suggested to explain all of the increase in malaria may be enhancing the impact of climate change.