The cost-efficiency of payments for environmental services (PES) to private landowners in the Osa Conservation Area, Costa Rica, is evaluated in terms of the trade-off between biodiversity representation and opportunity costs of conservation to agricultural and forestry land-use. Using available GIS data and an 'off-the-shelf' software application called TARGET, we find that the PES allocation criteria applied by authorities in 2002-2003 were more than twice as cost-efficient as criteria applied during 1999-2001. Results show that a policy relevant assessment of the cost-effectiveness of PES relative to other conservation policies can be carried out at regional level using available studies and GIS data. However, there are a number of data and conceptual limitations to using heuristic optimisation algorithms in the analysis of the cost-efficiency of PES. Site specific data on probabilities of land-use change, and a detailed specification of opportunity costs of farm land, labour and capital are required to use algorithms such as TARGET for ranking individual sites based on cost-efficiency. Despite its conceptual soundness for regional conservation analysis, biodiversity complementarity presents a practical challenge as a criterion for PES eligibility at farm level because it varies depending on the set of areas under PES contracts at any one time.