Urban infrastructure is heavily reliant on water distribution systems. Contaminants entering the water distribution systems (WDS) are one of the most dangerous events that may occur either deliberately or by accident. Water can become polluted with chemicals or biological agents as a result of water flow. This can cause sickness or even death among people who drink the water. Using an Early Warning Detection System (EWDS) is one of the most effective ways to minimize negative consequences on public health. EWDS are sensors that can reduce the damage due to detecting the contamination. The main challenge is to arrange the sensors in the network in the most efficient way. In this study, the Non-Dominated Sorted Genetic Algorithm-II (NSGA-II), a multi-objective optimization approach, is developed to determine the optimal placement of quality sensors in water distribution networks by balancing four conflicting objectives. 1. Sensor detection likelihood, 2. Sensor expected detection time, 3. Sensor detection redundancy, and 4. The affected population before detection. A contamination matrix with 1000 contaminants event was generated, which represented the total possible combinations of pollutants, then the optimal Pareto fronts are obtained for each two conflicting objectives. The importance coefficients are proposed and applied to minimize the pollution detection time and the number of infected populations based on the contamination risks and the node demands, respectively. Moreover, the sensitivity analysis of the results obtained from different objective functions related to the number of sensors installed in the network was conducted.