Improved prediction, prevention, and control of epidemics is a key technical element of the Roll Back Malaria partnership. We report a methodology for assessing the importance of climate as a driver of inter-annual variability in malaria in Botswana, and provide the evidence base for inclusion of climate information in a national malaria early warning system. The relationships of variability in rainfall and sea surface temperatures (SSTs) to malaria incidence are assessed at the national level after removing the impact of non-climatic trends and a major policy intervention. Variability in rainfall totals for the period December-February accounts for more than two-thirds of the inter-annual variability in standardized malaria incidence in Botswana (January-May). Both rainfall and annual malaria anomalies in December-February are significantly related to SSTs in the eastern Pacific, suggesting they may be predictable months in advance using seasonal climate forecasting methodologies.