Optimal design of a natural gas network, which is supposed to convey natural gas from a supply point in south of Iran to some delivery points in north and northwest of Iran, is presented in this paper. Sum of investment and operating costs constitutes the objective function of the present study. A wide range of design parameters, including the network layout, diameter of each pipeline, pressure value at each supply or delivery node, as well as number and locations of compressor stations (CSs) on each pipeline, were considered in the optimization problem. A Genetic Algorithm (GA) which exploits "optimal properties of single pipelines" was presented and used as the optimization tool. Short computation time and repeatability of results ensures achieving the global optimum solution and are positive features of the proposed optimization algorithm. The optimal network design obtained from the optimization procedure consisted of 2660 km of pipelines and 26 CSs. It required a total annual cost of about 366.15 M$/year. The results explain why the layout with the shortest total length is not the optimal choice. (C) 2013 The Institution of Chemical Engineers. Published by Elsevier B.V. All rights reserved.