The possible influence of Atlantic sea surface temperature (SST) on winter haze days in China at interannual and decadal time scales is investigated using the observed haze-day data from 329 meteorological stations, National Centers for Environmental Prediction-National Centers for Atmospheric Research (NCEP-NCAR) reanalysis, and a SST dataset for 1978–2012. Wintertime haze days in China show robust interannual variations and significant increases over time. The SST anomalies over the North Atlantic from summer to the following winter exhibit a significant in-phase relationship with winter haze days on both decadal and interannual time scales, whereas the anomalous negative-positive SSTs from north to south over the South Atlantic from autumn to the following winter show a significant positive relationship with winter haze days on the interannual time scale. The anomalous warm SST over the North Atlantic, i.e., the positive phase of the Atlantic multidecadal oscillation (AMO), corresponds to the positive phase of the Arctic oscillation (AO). This result implies that a stable mean flow and strong westerly anomalies exist over north China. The anomalous dipole pattern in the South Atlantic results in the abnormal southerly airflow in the troposphere over eastern China. Neither the westerly anomalies over north China nor the southerly anomalies over eastern China, which are associated with the North Atlantic and South Atlantic SST anomalies, respectively, are conducive to occurrences of cold air. Consequently, the weakened cold airflow from north of eastern China suppresses the dispersion of pollutants over China and results in above-normal haze days.