Among seabirds, the fregatids stand out with a high prevalence of blood parasites. Four of 5 species in this family have been found to be infected with Haemoproteus; however, complete species descriptions with molecular phylogeny are lacking. Seventy-five samples from 4 species of frigatebirds, i.e., Fregata andrewsi, Fregata minor, Fregata magnificens, and Fregata aquila, were screened for infections caused by species of Haemoproteus. Four different parasite haplotypes were found infecting frigatebirds based on the sequencing of a fragment of the cytochrome b gene. Two haplotypes belong to the subgenus Parahaemoproteus, and the other 2 correspond to haplotypes within the subgenus Haemoproteus. The more prevalent and cosmopolitan Parahaemoproteus haplotype (FregPHae1) was phylogenetically grouped with other Haemoproteus parasites infecting non-passerine birds, but it could not be detected from the single sample from F. aquila. The other Parahaemoproteus haplotype (FregPHae2) was not phylogenetically clustered with parasites infecting non-passerine birds, and it was sequenced from a single (1 each) F. andrewsi and F. minor. Blood smears from F. andrewsi infected only by FregPHae1 haplotype showed sufficient gametocytes to allow description of a new species, Haemoproteus valkiūnasi sp. nov. In contrast to Haemoproteus iwa, the only previously known blood parasite infecting frigatebirds and described from F. minor from Galapagos Islands, parasites from F. andrewsi (1) are shorter with no contact of gametocyte with host cell membrane, (2) have fewer pigment granules, and (3) have wider microgametocytes, with a smaller host nuclear displacement. In contrast, patent single infections corresponding to the cosmopolitan haplotype of the subgenus Haemoproteus (FregHae1) were also found in samples from 1 F. andrewsi, 1 F. minor, and 1 F. aquila. In all these cases, the number of microgametocytes was very low, resembling H. iwa, which lacks microgametocytes in the original description. Macrogametocytes of haplotype FregHae1 in F. andrewsi differ significantly from all the characteristics measured from H. valkiūnasi. In addition, it also differs from all characteristics of H. iwa despite being genetically identical in the analyzed fragment.