Abstract A systematic method is developed for supply reliability assessment of natural gas pipeline networks. In the developed method, the integration of stochastic processes, graph theory and thermal-hydraulic simulation is performed accounting for uncertainty and complexity. The supply capacity of a pipeline network depends on the unit states and the network structure, both of which change stochastically because of stochastic failures of the units. To describe this, in this work a capacity network stochastic model is developed, based on Markov modeling and graph theory. The model is embedded in an optimization algorithm to compute the capacities of the pipeline network under different scenarios and analyze the consequences of failures of units in the system. Indices of supply reliability and risk are developed with respect to two aspects: global system and individual customers. In the case study, a gas pipeline network is considered and the results are analyzed in detail.