In this study we use a global climate model to assess particulate matter (PM) variability induced by the North Atlantic Oscillation (NAO) in Europe during winter and the potential impact on human health of a future shift in the NAO mean state. Our study shows that extreme NAO phases in the 1990s modulated most of the interannual variability of winter PM concentrations in several European countries. Increased PM concentrations as a result of a positive shift in the mean winter NAO of one standard deviation would lead to about 5500 additional premature deaths in Mediterranean countries, compared to the simulated average PM health impact for the year 2000. In central-northern Europe, instead, higher wind speed and increased PM removal by precipitation lead to negative PM concentration anomalies with associated health benefits. We suggest that the NAO index is a useful indicator for the role of interannual atmospheric variability on large-scale pollution-health impacts.