Due to aging beyond the intended design life, many water mains in the USA are currently deteriorated resulting in an increasing number of failures which challenge water utilities with diminished supply reliabilities, loss of treated water, and numerous other societal issues. Water pipeline systems serving regions that are naturally vulnerable to external hazards, such as earthquakes, pose additional challenges. Numerous vulnerabilities such as these must be congruently analyzed for optimal capital improvement planning of water supply systems. A resilience-based rehabilitation planning framework is presented and demonstrated in this paper to coherently integrate the vulnerabilities of water pipelines to seismic hazards and natural deterioration. The artificial bee colony (ABC), shuffled frog leaping (SFLA), and genetic algorithms (GA) are investigated to identify the best performing optimization algorithm to be used in the modeling framework presented in this study. A scenario of a real-world water supply system operating in the earthquake-prone region in South Carolina is used for demonstrating the rehabilitation framework. The study approach and the presented findings will provide guidance to water utility professionals in optimal capital improvement planning to enhance supply resilience to a multitude of vulnerabilities.