Tropical forest conservation is considered a low-cost option for climate change mitigation. But mitigation cost assessments have featured opportunity costs, neglecting policy implementation costs. Here we use official data to identify the Brazilian federal government's operational and institutional budgets related to forest conservation policies implemented from 2000 to 2014. We distinguish the allocated and executed budgets of these policies, and provide scenario-based estimates of their cost-effectiveness. On average, Brazil spent US$ 1 billion/year on forest conservation policies at the federal level. Brazil's substantial reduction in annual forest loss after 2004 was accompanied by a higher operational budget execution of disincentive-based policy instruments, and an absolute increase in both allocated and executed institutional budgets. The post-2004 successful mitigation effort represented additional implementation costs to the Brazilian federal government of US$ 308–923/ha of avoided deforestation, or US$ 0.87–2.60/tCO2 of avoided emissions. Factoring in also approximate municipal and state expenditures, these costs increase to US$ 385–1153/ha or US$ 1.09–3.25/tCO2. We conclude that implementations costs are non-trivial in size, including compared to estimates of land users' opportunity costs. This has important implications for REDD + policy design, in the sense that implementation costs need to be adequately considered.