Air pollution has become an increasingly serious environmental problem in China. Especially in winter, the air pollution in northern China becomes even worse due to winter heating. The “coal to gas” policy, which uses natural gas to replace coal in the heating system in winter, was implemented in Beijing in the year 2013. However, the effects of this policy reform have not been examined. Using a panel dataset of 16 districts in Beijing, this paper employs a first difference model to examine the impact of the “coal to gas” policy on air quality. Strong evidence shows that the “coal to gas” policy has significantly improved the air quality in Beijing. On average, the “coal to gas” policy reduced sulfur dioxide (SO2), nitrogen dioxide (NO2), particulate matter smaller than 10 µm (PM10), particulate matter smaller than 2.5 µm (PM2.5) and carbon monoxide (CO) by 12.08%, 4.89%, 13.07%, 11.94% and 11.10% per year, respectively. We find that the “coal to gas” policy is more effective in areas with less energy use efficiency. The finding of this paper suggests that the government should continue to implement the “coal to gas” policy, so as to alleviate the air pollution in Beijing, China.