In maintaining the efficiency of water supply services, it is crucial to monitor the performance of water utilities in a country. One of widely used tools to evaluate the performance of water supply services is Data Envelopment Analysis (DEA). However, prior DEA-related approaches for water sector performance have ignored the internal structure of water supply service operations; i.e. the water treatment process and water distribution process. Another neglected aspect is the presence of Non-Revenue Water (NRW) to be considered as an undesirable output in the water distribution process. This is in line with the goal to reduce the NRW level in water supply systems. Hence, this paper proposed a two-stage Network DEA with the presence of undesirable output to evaluate the performance of Malaysian water utilities. This proposed method advances the existing DEA-based approach on water utility performance measurement, where not only the potential reduced level of NRW can be determined, but, a new performance benchmarking indicator regarding the concept of efficiency and effectiveness of the water supply industry in Malaysia can be established from the same model.