Parasites often have shorter generation times and, in some cases, faster mutation rates than their hosts, which can lead to greater population differentiation in the parasite relative to the host. Here we present a population genetic study of two ectoparasitic flies, Olfersia spinifera and Olfersia aenescens compared with their respective bird hosts, great frigatebirds (Fregata minor) and Nazca boobies (Sula granti). Olfersia spinifera is the vector of a haemosporidian parasite, Haemoproteus iwa, which infects frigatebirds throughout their range. Interestingly, there is no genetic differentiation in the haemosporidian parasite across this range despite strong genetic differentiation between Galapagos frigatebirds and their non-Galapagos conspecifics. It is possible that the broad distribution of this one H. iwa lineage could be facilitated by movement of infected O. spinifera. Therefore, we predicted more gene flow in both fly species compared with the bird hosts. Mitochondrial DNA sequence data from three genes per species indicated that despite marked differences in the genetic structure of the bird hosts, gene flow was very high in both fly species. A likely explanation involves non-breeding movements of hosts, including movement of juveniles, and movement by adult birds whose breeding attempt has failed, although we cannot rule out the possibility that closely related host species may be involved.