A Performance-Based Contract (PBC) for Non-Revenue Water (NRW) reduction was executed in the Muharraq Governorate of the Kingdom of Bahrain between 2013 and 2016. The contract included a mixture of fixed and performance-based payment terms. The performance element included the establishment of 35 District Metered Areas (DMAs) and the targeted reduction of NRW by 15 percentage points within the project catchment. The contract was a partnership between the contractor and the utility, whereby the contractor undertook the investigative work, while the utility was responsible for executing all resulting construction activities. A number of important lessons were learnt that should be applied to future projects. The contract design arguably placed too much risk upon the contractor. The original project timescale proved to be completely unrealistic. The data collected following DMA establishment enabled the cause of NRW in each DMA to be determined and the appropriate action taken. The quick win for real losses was automated pressure control, while permanent monitoring of large industrial users represented the same for apparent losses. Knowledge transfer to the utility proved to be arguably more important than achievement of contractual NRW targets. The contractor–utility working relationship proved crucial in facilitating eventual project success.