Multi-Objective Optimization methods and techniques are nowadays largely used and well known to be effective to approach both design and operational aspects of water distribution networks for urban potable water supply. When a WDN is also designed for firefighting purposes it is important that hydrants on the streets are capable to meet certain requirements in terms of adequate flow and pressure in order to feed firefighters’ trucks. The aim of this work is to present a rehabilitation strategy for deficient WDNs, involving pipe replacing by means of a Multi-Objective Optimization approach that takes into account single hydrant’s final performance and replacing costs, using a Pressure Driven Analysis for solving the hydraulics and a Greedy Algorithm to find Pareto Sets of optimal solutions for different fire locations. A Python 3.7.4 code for the purpose has been written. Pipe replacing is found to be effective in WDN rehabilitation problems and is also considered in other studies about firefighting-related optimization; it is also found to be common the use of DN 150 pipes in WDNs designed for firefighting too. An operational methodology about supply deficient networks with a certain probable amount of water from surroundings DMAs, when fire events occur, is also developed. Both methodologies are applied to the Benalúa’s WDN (Alicante, Spain), one of the NAIADES use cases. Rehabilitation results show hydrants’ performance improvements with affordable costs. This methodology can also be a helpful tool for decision makers, especially when dealing with very large and deficient networks.