Malaria is a major cause of morbidity and mortality in Mozambique. We present a malaria early warning system (MEWS) for Mozambique informed by seven years of weekly case reports of malaria in children under 5 years of age from 142 districts. A spatio-temporal model was developed based on explanatory climatic variables to map exceedance probabilities, defined as the predictive probability that the relative risk of malaria incidence in a given district for a particular week will exceed a predefined threshold. Unlike most spatially discrete models, our approach accounts for the geographical extent of each district in the derivation of the spatial covariance structure to allow for changes in administrative boundaries over time. The MEWS can thus be used to predict areas that may experience increases in malaria transmission beyond expected levels, early enough so that prevention and response measures can be implemented prior to the onset of outbreaks. The framework we present is also applicable to other climate-sensitive diseases.