The degree to which widespread avian blood parasites in the genera Plasmodium and Haemoproteus pose a threat to novel hosts depends in part on the degree to which they are constrained to a particular host or host family. We examined the host distribution and host-specificity of these parasites in birds from two relatively understudied and isolated locations: Australia and Papua New Guinea. Using polymerase chain reaction (PCR), we detected infection in 69 of 105 species, representing 44% of individuals surveyed (n = 428). Across host families, prevalence of Haemoproteus ranged from 13% (Acanthizidae) to 56% (Petroicidae) while prevalence of Plasmodium ranged from 3% (Petroicidae) to 47% (Ptilonorhynchidae). We recovered 78 unique mitochondrial lineages from 155 sequences. Related lineages of Haemoproteus were more likely to derive from the same host family than predicted by chance at shallow (average LogDet genetic distance = 0, n = 12, P = 0.001) and greater depths (average distance = 0.014, n = 11, P < 0.001) within the parasite phylogeny. Within two major Haemoproteus subclades identified in a maximum likelihood phylogeny, host-specificity was evident up to parasite genetic distances of 0.029 and 0.007 based on logistic regression. We found no significant host relationship among lineages of Plasmodium by any method of analysis. These results support previous evidence of strong host-family specificity in Haemoproteus and suggest that lineages of Plasmodium are more likely to form evolutionarily-stable associations with novel hosts.