The burden of malaria is heavily concentrated in sub-Saharan Africa (SSA) where cases and deaths associated with COVID-19 are rising. In response, countries are implementing societal measures aimed at curtailing transmission of SARS-CoV-2. Despite these measures, the COVID-19 epidemic could still result in millions of deaths as local health facilities become overwhelmed. Advances in malaria control this century have been largely due to distribution of long-lasting insecticidal nets (LLINs), with many SSA countries having planned campaigns for 2020. In the present study, we use COVID-19 and malaria transmission models to estimate the impact of disruption of malaria prevention activities and other core health services under four different COVID-19 epidemic scenarios. If activities are halted, the malaria burden in 2020 could be more than double that of 2019. In Nigeria alone, reducing case management for 6 months and delaying LLIN campaigns could result in 81,000 (44,000-119,000) additional deaths. Mitigating these negative impacts is achievable, and LLIN distributions in particular should be prioritized alongside access to antimalarial treatments to prevent substantial malaria epidemics.