Recent studies suggested increasing evidence of the linkage between Arctic sea ice changes and mid-latitude extreme weather events, including cold extremes with severe snowstorms in winter and heat extremes in summer. Here we investigated the linkage between winter air stagnation extremes—a type of extreme weather events with close relation with air pollution—in China and Arctic sea ice changes in preceding autumn and early winter. We constructed a synthetic air stagnation index named pollution potential index (PPI) and analyzed the temporal variation of PPI over eastern China in the past four decades. Statistical analysis revealed an increasing trend of regional PPI in winter with the largest increase in high percentiles, suggesting more and severer air stagnation extremes that were conducive to winter haze pollution in China. We then analyzed the statistical relationship between PPI and major climate factors using principal component analysis (PCA) and identified the largest contribution of Arctic sea ice changes to an unprecedented PPI extreme event in January, 2013. We designed multiple climate sensitivity experiments using the Whole Atmosphere Community Climate Model to evaluate this statistical relationship. The modeling results demonstrated more positive PPI extremes with stronger magnitude under the perturbed cryosphere conditions, especially when sea ice loss occurred in the Pacific sector of the Arctic (i.e., the East Siberian and Chukchi Seas). Dynamic diagnoses further revealed that declined regional sea ice increased upward sensible and latent heat fluxes in autumn and transient eddy fluxes in the vicinity of Scandinavia in winter, which amplified an atmospheric teleconnection pattern resembling the negative phase of the Eurasian (EU) pattern. The high pressure anomalies in the middle- and upper-troposphere over East Asia in the EU-like pattern deteriorated near surface ventilation conditions by weakening northwesterly monsoon winds and resulted in more and stronger air stagnation and pollution extremes. Consequently, similar extreme events will likely occur at a higher frequency during winter in China as a result of the changing boreal cryosphere, posing great challenges for winter haze pollution mitigation but providing a strong incentive for anthropogenic emission reduction.