Background: Parasites are evolutionary hitchhikers whose phylogenies often track the evolutionary history of their hosts. Incongruence in the evolutionary history of closely associated lineages can be explained through a variety of possible events including host switching and host independent speciation. However, in recently diverged lineages stochastic population processes, such as retention of ancestral polymorphism or secondary contact, can also explain discordant genealogies, even in fully co-speciating taxa. The relatively simple biogeographic arrangement of the Galapagos archipelago, compared with mainland biomes, provides a framework to identify stochastic and evolutionary informative components of genealogic data in these recently diverged organisms. Results: Mitochondrial DNA sequences were obtained for four species of Galapagos mockingbirds and three sympatric species of ectoparasites - two louse and one mite species. These data were complemented with nuclear EF1 alpha sequences in selected samples of parasites and with information from microsatellite loci in the mockingbirds. Mitochondrial sequence data revealed differences in population genetic diversity between all taxa and varying degrees of topological congruence between host and parasite lineages. A very low level of genetic variability and lack of congruence was found in one of the louse parasites, which was excluded from subsequent joint analysis of mitochondrial data. The reconciled multi-species tree obtained from the analysis is congruent with both the nuclear data and the geological history of the islands. Conclusions: The gene genealogies of Galapagos mockingbirds and two of their ectoparasites show strong phylogeographic correlations, with instances of incongruence mostly explained by ancestral genetic polymorphism. A third parasite genealogy shows low levels of genetic diversity and little evidence of co-phylogeny with their hosts. These differences can mostly be explained by variation in life-history characteristics, primarily host specificity and dispersal capabilities. We show that pooling genetic data from organisms living in close ecological association reveals a more accurate phylogeographic history for these taxa. Our results have implications for the conservation and taxonomy of Galapagos mockingbirds and their parasites.