When parasite evolution follows the evolution of hosts, cophylogenies can occur. Cophylogenies are when parasite and host phylogenies look like mirror images of each other; at every host speciation event, the parasites have also speciated. This is typically assumed to occur more frequently with vertically transmitted parasites (e.g., lice) than with vector-transmitted parasites (e.g., haemosporidian parasites). However, analyses have often been conducted with poorly resolved phylogenies of both hosts and parasites, bringing previous conclusions into question. Haemoproteus parasites are blood parasites of birds that are transmitted by biting midges and are related to human malaria parasites. They are typically more host-specific than other related genera (e.g., Plasmodium and Leucocytozoon). Here, we use next-generation sequencing to build a whole mitochondrial genome phylogeny of a clade of Haemoproteus parasites of Acrocephalus warblers. We then constructed a host phylogeny using five genes available in the literature. We used these well resolved phylogenies to test for a cophylogenetic signal using several statistical approaches. We found limited evidence of a cophylogenetic relationship between the parasites and their hosts, suggesting frequent host-shifting, likely due to the generalist biting nature of their vectors. Our results are consistent with the idea that vector-transmitted parasites do not speciate with their hosts. Next-generation sequence data allow us to generate robust phylogenies, thus providing improved statistical power when revisiting previously difficult to test hypotheses.