Natural gas, as a cleaner fossil fuel energy resource, is playing an increasingly important role in the futureenergy mix to achieve emission reduction target globally. In this study, a new method based on the exter-nal cost is developed to identify an optimal solution for natural gas distribution. China is selected for acase study. Both the economic cost and the external cost of pollutant emissions have been considered.The provincial distribution of natural gas and other energy resources is optimized with the aim to min-imize both economic and external costs. Results show that the supply of natural gas should be prioritizedfor Beijing, Tianjin and Shanghai, owing to higher external costs and the optimized distribution canreduce the overall external cost by 4% in China. The optimization of natural gas distribution will alsoinfluence CO2emissions, therefore, the determination of the reduction target for each province shouldconsider the external cost. Sensitivity study also shows that the minimum energy demand, the maximumnatural gas supply and the minimum natural gas demand are the key parameters that impact the opti-mized distribution for each province.