Saharan dust intrusions strongly impact Atlantic and Mediterranean coastal regions. Today, most operational dust forecasts extend only 2–5 days. Here we show that on timescales of weeks to months, North African dust emission and transport are impacted by sudden stratospheric warmings (SSWs), which establish a negative North Atlantic Oscillation-like surface signal. Chemical transport models show a large-scale dipolar dust response to SSWs, with the burden in the Eastern Mediterranean enhanced up to 30% and a corresponding reduction in West Africa. Observations of inhalable particulate (PM10) concentrations and aerosol optical depth confirm this dipole. On average, a single SSW causes 680–2460 additional premature deaths in the Eastern Mediterranean and prevents 1180–2040 premature deaths in West Africa from exposure to dust-source fine particulate (PM2.5). Currently, SSWs are predictable 1–2 weeks in advance. Altogether, the stratosphere represents an important source of subseasonal predictability for air quality over West Africa and the Eastern Mediterranean.