Genetic divergence and speciation in plant-feeding insects could be driven by contrasting selection pressures imposed by different plant species and taxa. While numerous examples of host-associated differentiation (HAD) have been found, the overall importance of HAD in insect diversification remains unclear, as few studies have investigated its frequency in relation to all speciation events. One promising way to infer the prevalence and repeatability of HAD is to estimate genetic differentiation in multiple insect taxa that use the same set of hosts. To this end, we measured and compared variation in mitochondrial COI and nuclear ITS2 sequences in population samples of leaf-galling Pontania and bud-galling Euura sawflies (Hymenoptera: Tenthredinidae) collected from six Salix species in two replicate locations in northern Fennoscandia. We found evidence of frequent HAD in both species complexes, as individuals from the same willow species tended to cluster together on both mitochondrial and nuclear phylogenetic trees. Although few fixed differences among the putative species were found, hierarchical AMOVAs showed that most of the genetic variation in the samples was explained by host species rather than by sampling location. Nevertheless, the levels of HAD measured across specific pairs of host species were not correlated in the two focal galler groups. Hence, our results support the hypothesis of HAD as a central force in herbivore speciation, but also indicate that evolutionary trajectories are only weakly repeatable even in temporally overlapping radiations of related insect taxa.