Due to the asymmetry of information on the potential of coal reduction in each province, Chinese coal reduction plans and “coal-to-gas” policy are often not well-implemented. In this study, we proposed a nonparametric production frontier model to calculate the potential for coal reduction. Compared with the existing research, the model has many advantages, distinguishing between clean and dirty energy and reflecting the Kaldor-Hicks improvement in energy substitution. Based on China's provincial panel data from 2006 to 2017, this study uses the above model to measure the utilization efficiency and saving potential of coal and the effect of “coal-to-gas” transition. The results demonstrate that many provinces close to coal-producing areas, such as Shanxi, Shandong, Henan, and Hebei, have great potential for coal reduction, and should be the focus of the coal reduction policy. Shandong Province has the most additional coal savings due to “coal-to-gas”, and its effect is good in the northeast and some provinces in southern China, but not in most western provinces. The calculation results can help China's central government formulate a coal reduction incentive plan.