Product quality and uncertainty, e.g. of demand, quality etc., are two important issues in the long-term planning of natural gas production systems. This paper presents a stochastic pooling problem formulation to address these two issues, where the qualities of the flows in the system are described with a pooling model and the uncertainty in the system is handled via a multi-scenario, two-stage stochastic recourse approach. The advantages of the proposed formulation are demonstrated with a gas network planning problem case study. The stochastic pooling problem is a nonconvex Mixed-Integer Nonlinear Programming (MINLP) problem which is solved in this paper by a commercial MINLP solver, BARON [1]. The computational study shows that the solution time with BARON increases dramatically with the number of scenarios.