**Abstract** Agroforestry can contribute to an increase in tree cover in historically forested tropical landscapes with associated gains in biodiversity and ecosystem functioning, but only if established on open land instead of underneath a forest canopy. However, declines in yields with increasing shade are common across agroforestry crops, driving shade-tree removal in forest-derived agroforests and hindering tree regrowth in open-land-derived agroforests. To understand trajectories of change in tree cover in forest- and open-land-derived agroforests and the impacts of tree cover on vanilla yields, we studied 209 vanilla agroforests along an 88-year chronosequence in Madagascar. Additionally, we used remotely-sensed canopy cover data to investigate tree cover change in the agricultural landscape. We found yields to vary widely but independently of canopy cover and land-use history (forest- vs. open-land-derived), averaging at 154.6 kg ha^-1 yr^-1 (*SD* = 186.9). Furthermore, we found that forest- and open-land-derived vanilla agroforests gained canopy cover over time, but that only open-land-derived agroforests gained canopy height. Canopy cover increased also at the landscape scale: areas in the agricultural landscape with medium initial canopy cover gained 6.4% canopy cover over 10 years, but canopy cover decreased in areas with high initial canopy cover. These opposing trends suggest tree cover rehabilitation across areas covered by vanilla agroforests, whereas remnant forest fragments in the agricultural landscape were transformed or degraded. Our results indicate that yield-neutral tree rehabilitation through open-land-derived agroforestry could, if coupled with effective forest protection, provide mutually beneficial outcomes for ecosystem functions and agricultural production in a smallholder-dominated agricultural landscape.