Studies on the determinants of plant–herbivore and herbivore–parasitoid associations provide important insights into the origin and maintenance of global and local species richness. If parasitoids are specialists on herbivore niches rather than on herbivore taxa, then alternating escape of herbivores into novel niches and delayed resource tracking by parasitoids could fuel diversification at both trophic levels. We used DNA barcoding to identify parasitoids that attack larvae of seven Pontania sawfly species that induce leaf galls on eight willow species growing in subarctic and arctic–alpine habitats in three geographic locations in northern Fennoscandia, and then applied distance- and model-based multivariate analyses and phylogenetic regression methods to evaluate the hierarchical importance of location, phylogeny and different galler niche dimensions on parasitoid host use. We found statistically significant variation in parasitoid communities across geographic locations and willow host species, but the differences were mainly quantitative due to extensive sharing of enemies among gallers within habitat types. By contrast, the divide between habitats defined two qualitatively different network compartments, because many common parasitoids exhibited strong habitat preference. Galler and parasitoid phylogenies did not explain associations, because distantly related arctic–alpine gallers were attacked by a species-poor enemy community dominated by two parasitoid species that most likely have independently tracked the gallers’ evolutionary shifts into the novel habitat. Our results indicate that barcode- and phylogeny-based analyses of food webs that span forested vs. tundra or grassland environments could improve our understanding of vertical diversification effects in complex plant–herbivore–parasitoid networks.