Time series models of malaria cases can be applied to forecast epidemics and support proactive interventions. Mosquito life history and parasite development are sensitive to environmental factors such as temperature and precipitation, and these variables are often used as predictors in malaria models. However, malaria-environment relationships can vary with ecological and social context. We used a genetic algorithm to optimize a spatiotemporal malaria model by aggregating locations into clusters with similar environmental sensitivities. We tested the algorithm in the Amhara Region of Ethiopia using seven years of weekly Plasmodium falciparum data from 47 districts and remotely-sensed land surface temperature, precipitation, and spectral indices as predictors. The best model identified six clusters, and the districts in each cluster had distinctive responses to the environmental predictors. We conclude that spatial stratification can improve the fit of environmentally-driven disease models, and genetic algorithms provide a practical and effective approach for identifying these clusters. •Time series of malaria risk in the Amhara region of Ethiopia can be modeled with remotely-sensed environmental covariates.•Responses to the environment are not spatially uniform and the region needs to be partitioned into separate models.•A genetic algorithm successfully partitioned districts into clusters with different responses to lagged environmental data.•Patterns of malaria outbreaks and their environmental drivers varied geographically along a precipitation gradient.