**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 inside forest. However, trade-offs between shade and crop yields are common across many agroforestry crops, driving shade-tree loss in forest-derived agroforests and hindering tree rehabilitation in open-land-derived agroforests. To investigate whether this common dynamic plays a role in vanilla agroforests, we studied 209 vanilla agroforests along an 88-year chronosequence in Madagascar and used remotely-sensed canopy cover data to investigate tree rehabilitation 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 open-land-derived vanilla agroforests gained 32.6% canopy cover over 60 years, whereas forest-derived agroforests only gained 14.2%. Canopy cover increased also at the landscape scale: Areas in the agricultural landscape with medium initial canopy cover gained 6.4% canopy cover from 2000 to 2010, but areas with high initial canopy cover lost canopy cover. These opposing trends suggest tree rehabilitation across areas covered by vanilla agroforests, whereas remnant forest fragments in the agricultural landscape were transformed or degraded. Overall, forest-dependent ecosystem functions may thus suffer while functions provided by areas with medium canopy cover may benefit. Our results suggest that yield-neutral tree rehabilitation through agroforestry could, if coupled with effective forest protection, provide a win-win situation for ecosystem functions and agricultural production in smallholder-dominated agricultural landscapes.