Declining plant diversity alters ecological networks, such as plant–herbivore interactions. However, our knowledge of the potential mechanisms underlying effects of plant species loss on plant–herbivore network structure is still limited. We used DNA barcoding to identify herbivore–host plant associations along declining levels of tree diversity in a large-scale, subtropical biodiversity experiment. We tested for effects of tree species richness, host functional and phylogenetic diversity, and host functional (leaf trait) and phylogenetic composition on species, phylogenetic and network composition of herbivore communities. We found that phylogenetic host composition and related palatability/defence traits but not tree species richness significantly affected herbivore communities and interaction network complexity at both the species and community levels. Our study indicates that evolutionary dependencies and functional traits of host plants determine the composition of higher trophic levels and corresponding interaction networks in species-rich ecosystems. Our findings highlight that characteristics of the species lost have effects on ecosystem structure and functioning across trophic levels that cannot be predicted from mere reductions in species richness.