We compared patterns of mitochondrial DNA (mtDNA) differentiation in three host-specific lice (Halipeurus abnormis, Austromenopon echinatum and Saemundssonia peusi) and one generalist flea (Xenopsylla gratiosa), parasitizing 22 colonies of Cory's and Cape Verde shearwater (Calonectris). The shearwater hosts show distinct phylogeographic structure corresponding to the three taxa Calonectris d. diomedea, C. d. borealis, and C. edwardsii. The host-specific lice appeared undifferentiated among the three Calonectris taxa, whereas the more generalist flea displayed significant levels of population differentiation. Neither genetic distances among host populations, nor their spatial distribution explained the patterns of genetic variability observed in the ectoparasites. The lack of differentiation among lice is unexpected, given that previous work has found evidence of cospeciation between procellariiform seabirds and their lice, and lice typically have an elevated rate of mtDNA evolution with respect to their hosts. Our results suggest that either rates of evolution in seabird lice are not always as high as previously thought, or that the magnitude of movement of lice between seabird hosts has been substantially underestimated.