Coal is the dominating fuel for heating, resulting in serious air pollution in China especially in winter. To mitigate the problem, Chinese government has issued policies to motivate consumers to use natural gas to replace coal. Considering the high price of natural gas, in order to further promote the utilization of natural gas, this paper has proposed a new method that considers the external cost of fuel when optimizing the energy structure for space heating. The external cost is commonly used to reflect the impacts of pollutant emissions to measure social benefit. The proposed method has been applied to a case study for the regions of Beijing and Tianjin. Results show that optimizing the fuel consumption in Beijing and Tianjin as a whole can reduce the external cost by 36 million dollars.