Payments for Ecosystem Services (PES) aim to incentivize land users to manage their land in ways which benefit society. However, as with many complex socio-ecological interventions, robust evaluation of PES is challenging and rare. Using a Randomized Control Trial (RCT) we evaluate whether a conservation program in the Bolivian Andes, which incentivizes landowners to avoid deforestation and exclude cattle from riparian forests, delivers improvements in microbial water quality (as measured by Escherichia coli contamination), and reduces deforestation. Baseline data was collected in 2010 in 129 communities which were then randomly allocated to a treatment or control group. The evaluation ran until 2016. Presence of cattle feces adversely affected microbial water quality, showing the effectiveness of excluding cattle, but the intervention itself did not have a demonstrable effect at the landscape scale. Using Global Forest Change data, we show that the intervention (especially at higher levels of uptake) does appear to reduce deforestation (once past deforestation and other geographical predictors are taken into account). Program effectiveness is fundamentally an empirical question so well-designed field studies are needed. We highlight some of the challenges encountered in using this pioneering RCT to robustly evaluate a large-scale conservation interventions but conclude that such randomized approaches have an important role to play in contributing to the evidence base available to decision-makers.