Attention to tenure is a fundamental step in preparation for REDD+ implementation. Unclear and conflicting tenure has been the main challenge faced by the proponents of subnational REDD+ initiatives, and accordingly, they have expended much effort to remedy the problem. This article assesses how well REDD+ has performed in laying an appropriate tenure foundation. Field research was carried out in two phases (2010–2012 and 2013–2014) in five countries (Brazil, Peru, Cameroon, Tanzania, Indonesia) at 21 subnational initiatives, 141 villages (half targeted for REDD+ interventions), and 3,754 households. Three questions are posed: 1) What was the effect of REDD+ on perceived tenure insecurity of village residents?; 2) What are the main reasons for change in the level of tenure insecurity and security from Phase 1 to Phase 2 perceived by village residents in control and intervention villages?; and 3) How do intervention village residents evaluate the impact of tenure-related interventions on community well-being? Among the notable findings are that: 1) tenure insecurity decreases slightly across the whole sample of villages, but we only find that REDD+ significantly reduces tenure insecurity in Cameroon, while actually increasing insecurity of smallholder agricultural land tenure in Brazil at the household level; 2) among the main reported reasons for increasing tenure insecurity (where it occurs) are problems with outside companies, lack of title, and competition from neighboring villagers; and 3) views on the effect of REDD+ tenure-related interventions on community well-being lean towards the positive, including for interventions that restrain access to forest. Thus, while there is little evidence that REDD+ interventions have worsened smallholder tenure insecurity (as feared by critics), there is also little evidence that the proponents’ efforts to address tenure insecurity have produced results. Work on tenure remains an urgent priority for safeguarding local livelihoods as well as for reducing deforestation. This will require increased attention to participatory engagement, improved reward systems, tenure policy reform, integration of national and local efforts, and “business-as-usual” interests.