The development of Bio-Natural Gas (BNG) is of great strategic significance in alleviating the shortage of fossil natural gas and fostering low-carbon energy transition. This work shows the economic and environmental analysis of the straw-based BNG supply chain using a Mixed Integer Linear Programming (MILP) model. Considering a sustainable supply chain framework, including straw collection, transportation, pre-treatment and product, and technologies (e.g., Anaerobic Digestion and Gasification), the optimal alternative is determined. Different straw harvesting rates and carbon emission reduction targets are designed to evaluate the cost and carbon emissions of each routine. The proposed model is applied to a country case study in China to illustrate the optimization of a regional straw-based BNG supply chain. The results show that the minimal cost ranges from 6.02 to 8.55 RMB/m3, and the emission reduction potential is from 9.82 to 12.74 kg/m³. The use of straw-based BNG can generate environmental benefits and estimate costs.