Restoring native vegetation in agricultural landscapes can reverse biodiversity declines via species gains. Depending on whether the traits of colonizers are complementary or redundant to the assemblage, species gains can increase the efficiency or stability of ecological functions, yet detecting these processes is not straightforward. We propose a new conceptual model to identify potential changes to complementarity and redundancy in response to landscape change via relative changes in taxonomic and functional richness. We applied our model to a 14-year study of birds across an extensive agricultural region. We found compelling evidence that high levels of landscape-scale tree cover and patch-scale restoration were significant determinants of functional change in the overall bird assemblage. This was true for every one of the six traits investigated individually, indicating increased trait-specific functional complementarity and redundancy in the assemblage. Applying our conceptual model to species diversity data provided new insights into how the return of vertebrates to restored landscapes may affect ecological function.