Pervasive tenure insecurity in developing countries is a key challenge for REDD+. Brazil, a leader in REDD+, has advanced efforts to link forest tenure reform and environmental compliance. We describe how these policies have shaped sub-national interventions with detailed data on land tenure and livelihoods in four REDD+ pilot sites in the Brazilian Amazon. Despite different local contexts, REDD+ proponents have converged on a similar strategy of collaborating with government agencies to clarify tenure and pave the way for a mix of regulatory enforcement and incentive-based REDD+ mechanisms. This polycentric governance model holds promise for effective and equitable REDD+ implementation.