To better understand the interannual variation of winter haze pollution, this paper investigates winter circulation types and their impacts on local meteorological conditions and haze pollution during 38 winters from 1980 to 2017 in Beijing. Circulation types were classified by T-mode principal component analysis combined with the K-means cluster method using European Centre for Medium-range Weather Forecasts ERA-interim sea level pressure data. The results can significantly distinguish the cold air process, a degeneration of cold air, and stagnant weather. The cold air process over Beijing was accompanied by a low temperature, high relative humidity, large pressure gradient and near-surface wind speed, and deep mixing layer. The cold air process facilitated pollutant dispersion and transport to the outside (such as East China, Bohai Sea, and Yellow Sea) and formed low PM2.5 concentrations and low frequencies of haze days. In contrast, the local meteorology and haze pollution were almost the inverse for stagnant weather. The local meteorological conditions and haze pollution for the degeneration of cold air are between the previous circulation types. Considering PM2.5 observation during 2010–2017, the occurrence frequency of cold air was low in the recent winters of 2013, 2014 and 2017, and resulted in severe PM2.5 pollution. High frequency of stagnant weather (48.4%) was one of the reasons that haze pollution reached 37% during 38 winters from 1980 to 2017 over Beijing. The time series of haze frequency was negatively correlated with that of cold air frequency. Winter haze pollution was affected by climate change over Beijing. During 38 winters from 1980 to 2017, a decreased trend of haze days was found, which was partly related to an increased trend of cold air frequency. However, the trends of haze days and cold air in Beijing were not significant based on regression analysis.