Air quality in eastern China has becoming more and more worrying in recent years, and haze is now No.1 air pollution issue. Results in this study show the decreasing Arctic sea ice (ASI) is an important contributor to the recent increased haze days in eastern China. The authors find that the number of winter haze days (WHD) in eastern China is strongly negatively correlated with the preceding autumn ASI during 1979–2012, and about 45%–67% of the WHD interannual to interdecadal variability can be explained by ASI variability. Following previous studies on the impact of ASI loss on the northern hemisphere climate, the authors’ studies further reveal that the reduction of autumn ASI leads to positive sea-level pressure anomalies in mid-latitude Eurasia, northward shift of track of cyclone activity in China, and weak Rossby wave activity in eastern China south of 40?N during winter season. These atmospheric circulation changes favor less cyclone activity and more stable atmosphere in eastern China, leading to more haze days there. Furthermore, the patterns of circulation changes associated with autumn ASI and WHD are in very good agreement over the East Asia, particularly in eastern China. The authors suggest that haze pollution may continue to be a serious issue in the near future as the decline of ASI continues under global warming.