With the increasing proportion of natural gas in power generation, natural gas network and electricity network are closely coupled. Therefore, planning of any individual system regardless of such interdependence will increase the total cost of the whole combined systems. Therefore, a multi-objective optimization model for the combined gas and electricity network planning is presented in this work. To be specific, the objectives of the proposed model are to minimize both investment cost and production cost of the combined system while taking into account the N-1 network security criterion. Moreover, the stochastic nature of wind power generation is addressed in the proposed model. Consequently, it leads to a mixed integer non-linear, multi-objective, stochastic programming problem. To solve this complex model, the Elitist Non-dominated Sorting Genetic Algorithm II (NSGA-II) is employed to capture the optimal Pareto front, wherein the Primal-Dual Interior-Point (PDIP) method combined with the point estimate method is adopted to evaluate the objective functions. In addition, decision makers can use a fuzzy decision making approach based on their preference to select the final optimal solution from the optimal Pareto front. The effectiveness of the proposed model and method are validated on a modified IEEE 24-bus electricity network integrated with a 15-node natural gas system as well as a real-world system of Hainan province. (C) 2015 The Authors. Published by Elsevier Ltd.