A water distribution network is the most expensive component of a water supply system; consequently, the overall planning, installation, and rehabilitation processes should be implemented accurately and carefully. The main issue that developing countries are facing is how to optimize the distribution network to meet increasing water demand. To tackle the issue, this paper proposes a new concept for rehabilitation and expansion of a water distribution network while ensuring cost-effectiveness and adequate water pressure. The main framework of the pipe network is formulated based on the concept of a ‘trunk/limb mains reinforced pipe system’. Reinforcement of trunk/limb mains in the network is carried out selectively, requiring proper selection of pipelines and of trunk/limb pipe diameters. A multi-step genetic algorithm was developed to obtain the objective of selecting an optimal solution design for pipeline selection and trunk/limb mains diameters. To clarify the effectiveness of this concept, cost analysis was performed. The result indicates that application of this method offers advantages for rehabilitation and expansion, in that not only meeting increasing water demand but also cost-effectiveness and desirable hydraulic conditions can be achieved in the network.