Blood parasites of the sub-genus Haemoproteus have been reported in seabirds, in particular in species in the Suliformes order. These parasites are transmitted by hippoboscid flies of the genus Olfersia; strong specificity has been suggested between the vector and its vertebrate host. We investigated the prevalence of Haemoproteus infection in Suliformes and hippoboscid flies in two oceanic islands of the Western Indian Ocean: Europa and Tromelin. In total, 209 blood samples were collected from great frigatebirds (Fregata minor), masked boobies (Sula dactylatra) and red-footed boobies (Sula sula). Forty-one hippoboscid flies were also collected from birds. Seventeen frigatebirds and one fly collected on Europa tested positive for the presence of Haemoproteus parasites by polymerase chain reaction. Phylogenetic analyses based on partial sequences of the Cytochrome b gene showed that parasites were closely related to Haemoproteus iwa reported from frigatebirds in the Pacific Ocean and in the Caribbean. Plasmodium was also detected in a frigatebird on Europa; however, its placement on the phylogenetic tree could not be resolved. We provide strong support for transmission of blood parasites in seabirds in the Western Indian Ocean and suggest that migrations between the Pacific and the Indian oceans could favor the large-scale distribution of Haemoproteus iwa in frigatebird populations.