The reliability of a natural gas system involves the capacity of the supply, transportation, storage and distribution system to provide service without short-term interruptions in the event of contingencies. Typically, increasing the gas supply reliability implies diversification of gas sources, transportation redundancies or larger gas storage capabilities. In addition, the combined operative uncertainty of the transportation pipeline and gas supply are not considered when assessing the impact of new infrastructure seeking to increase the gas supply reliability. To overcome these deficiencies, we propose: (i) a stochastic cost-benefit analysis; (ii) a pipeline contingency model using topographical, societal (violence) and pipeline information; and (iii) a supply contingency model of scheduled and unscheduled maintenance. Moreover, we consider both the gas supply and transportation uncertainties using a Monte Carlo simulation and an optimization model; furthermore, the expected cost-benefit is estimated. Our methodology is applied and calibrated to the Colombian natural gas system to estimate the expected cost-benefit of a new pipeline: Jobo – Medellín. The results show that the expected benefit-cost ratio (BCR) of this pipeline is 2.02 and that the probability of having an economic benefit greater than the cost is equal to 99.0%.