Many engineering problems involve optimization of multiple and competing objectives. Conventionally, analysts have treated these problems as single objective optimization problems instead of multi-objective ones. In multi-objective optimization, there is not a single optimum but a set of trade-off solutions known as Pareto-optimal, non-dominated or non-inferior solutions. Recognizing the multi-objective nature of the rehabilitation problem of water supply distribution networks, this paper presents an application of an elitist multi-objective evolutionary algorithm, namely, Strength Pareto Evolutionary Algorithm (SPEA), to generate a series of non-dominated solutions. The rehabilitation analyses were conducted on a simple hypothetical network for minimum cost, minimum pressure requirement and maximum hydraulic benefit, dealt with a three-objective problem. Analyses were performed to identify suitable crossover and mutation operators as well as parameters to this rehabilitation problem, for which SPEA presented high performance in producing Pareto fronts.