Water distribution networks (WDNs) are vital parts of the urban infrastructure, and their construction, operation, and maintenance incur major investments. Therefore, many different approaches for optimizing WDNs exist. However, when it comes to large real WDNs, computational time becomes a significant factor, as the possible number of potential solutions grows exponentially. This paper discusses a highly efficient approach for Pareto-optimal design of WDNs based on complex network analysis (CNA). A real WDN with about 4,000 pipes (decision variables) was optimized first using a straightforward evolutionary algorithm approach with two objectives being cost minimization and resilience maximization. By systematically investigating topological features of the obtained Pareto-optimal solutions, insights into optimal networks are generated and a new design approach based on CNA is developed, which outperforms the results of the evolutionary algorithm. The proposed CNA approach is then successfully used to optimize a WDN with the same objectives where the evolutionary algorithm approach is computationally infeasible (semi-real case study with 157,040 decision variables).