Cost-effectiveness is an important aspect in the assessment of payments for environmental services (PES) initiatives. In participatory field trials with communities in Western Kenya, we combined procurement auctions for forest enrichment contracts with performance-based payments and compared the outcomes with a baseline scenario currently used by the Kenyan Forest Service. Procurement auctions were the most cost-effective. The competitive nature of the auction reduced contracting expenses (provision costs), and the result-oriented payments provided additional incentives to care for the planted seedlings, resulting in their improved survival rates (service quantity). These gains clearly exceeded increases in transaction costs associated with conducting an auction. The number of income-poor auction participants and winners was disproportionately high and local institutional buy-in was remarkably strong. Our participatory approach may, however, require adaptations when conducted at a larger scale. Although the number of contracts we monitored was limited and prohibited the use of statistical tests, our study is one of the first to reveal the benefits of using auctions for PES in developing countries.