Hemoparasites of the apicomplexan family Plasmodiidae include the etiological agents of malaria, as well as a suite of non-human primate parasites from which the human malaria agents evolved. Despite the significance of these parasites for global health, little information is available about their ecology in multi-host communities. Primates were investigated in Kibale National Park, Uganda, where ecological relationships among host species are well characterized. Blood samples were examined for parasites of the genera Plasmodium and Hepatocystis using microscopy and PCR targeting the parasite mitochondrial cytochrome b gene, followed by Sanger sequencing. To assess co-infection, “deep sequencing” of a variable region within cytochrome b was performed. Out of nine black-and-white colobus (Colobus guereza), one blue guenon (Cercopithecus mitis), five grey-cheeked mangabeys (Lophocebus albigena), 23 olive baboons (Papio anubis), 52 red colobus (Procolobus rufomitratus) and 12 red-tailed guenons (Cercopithecus ascanius), 79 infections (77.5%) were found, all of which were Hepatocystis spp. Sanger sequencing revealed 25 different parasite haplotypes that sorted phylogenetically into six species-specific but morphologically similar lineages. “Deep sequencing” revealed mixed-lineage co-infections in baboons and red colobus (41.7% and 64.7% of individuals, respectively) but not in other host species. One lineage infecting red colobus also infected baboons, but always as the minor variant, suggesting directional cross-species transmission. Hepatocystis parasites in this primate community are a diverse assemblage of cryptic lineages, some of which co-infect hosts and at least one of which can cross primate species barriers.