Product quality and uncertainty are two important issues in the design and operation of natural gas production networks. This paper presents a stochastic pooling problem optimization 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 with a multi-scenario, two-stage stochastic recourse approach. In addition, multi-objective problems are handled via a hierarchical optimization approach. The advantages of the proposed formulation are demonstrated with case studies involving an example system based on Haverly's pooling problem and a real industrial system. The stochastic pooling problem is a potentially large-scale nonconvex Mixed-Integer Nonlinear Program (MINLP), and a rigorous decomposition method developed recently is used to solve this problem. A computational study demonstrates the advantage of the decomposition method over a state-of-the-art branch-and-reduce global optimizer, BARON. (C) 2010 American Institute of Chemical Engineers AIChE J, 57: 2120-2135, 2011