Background: Numerous studies have investigated cospeciation between parasites and their hosts, but there have been few studies concerning parasitoids and insect hosts. The high diversity and host specialization observed in Anicetus species suggest that speciation and adaptive radiation might take place with species diversification in scale insect hosts. Here we examined the evolutionary history of the association between Anicetus species and their scale insect hosts via distance-based and tree-based methods. Results: A total of 94 Anicetus individuals (nine parasitoid species) and 113 scale insect individuals (seven host species) from 14 provinces in China were collected in the present study. DNA sequence data from a mitochondrial gene (COI) and a nuclear ribosomal gene (28S D2 region) were used to reconstruct the phylogenies of Anicetus species and their hosts. The distance-based analysis showed a significant fit between Anicetus species and their hosts, but tree-based analyses suggested that this significant signal could be observed only when the cost of host-switching was high, indicating the presence of parasite sorting on related host species. Conclusions: This study, based on extensive rearing of parasitoids and species identification, provides strong evidence for a prevalence of sorting events and high host specificity in the genus Anicetus, offering insights into the diversification process of Anicetus species parasitizing scale insects.