Population growth is one of the most challenging factors around the design, operation, and renewal of water distribution systems (WDS). Nowadays, cities are subjected to many dramatic changes that may disturb the performance and original approach of urban infrastructure; among these are the informal settlements (slums) and overcrowding phenomena. This paper describes a rehabilitation methodology of real WDS that seeks to identify the proper topology changes, in terms of pipes replacement, under different demand scenarios in order to readjust the network, achieve minimum pressure requirement, and improve the hydraulic performance of the whole system. This research focuses in the assessment of two rehabilitation criteria, tested in two WDSs of different Colombian towns and three district metering area (DMA) of main Colombian cities, with an infrastructure installed at least twenty years ago. Some surrogate measures of networks reliability were taken into account to assess the rehabilitation methodology, and its results were compared with optimal designs. The EPANET toolkit, MATLAB, and REDES software were used in this research. Both criteria proved to be. Both criteria proved to be good benchmarks to improve some performance indicators in each rehabilitated network. Finally, the suitability of each criteria was analysed considering the topologic complexity as well as network capital cost.