The honey-bee mating optimization (HBMO) algorithm is applied to extracting the optimal rehabilitation strategy for water distribution systems. Deterioration of water distribution networks due to aging and stress, causes increased operation and maintenance costs, water losses, reduction in the quality of service, and reduction in the quality of water supplied. Since the most expensive component of water supply systems is the distribution network, their increased costs can be substantial. A well-known two-loop network is presented to demonstrate the application of the proposed algorithm. The significance of this algorithm is its ability to identify an optimal rehabilitation strategy in a combinatorial solution space considering the deterioration of both structural integrity and hydraulic capacity of the entire network. A previously developed methodology is presented to implement this approach into a decision support system which facilitates the identification of an optimal rehabilitation strategy. The problem is considered as the present value of an infinite stream of costs for 30 and 100 operational years. The results indicate that the proposed HBMO algorithm readily finds the feasible solution for the problem and goes towards the optimal solution. Furthermore, results prove the cost-effectiveness of such a strategy compared with those not considering the rehabilitation strategy.