Haemosporida parasites of even-toed ungulates are diverse and globally distributed, but since their discovery in 1913 their characterization has relied exclusively on microscopy-based descriptions. In order to bring molecular approaches to bear on the identity and evolutionary relationships of ungulate malaria parasites, we conducted Plasmodium cytb-specific nested PCR surveys using blood from water buffalo in Vietnam and Thailand, and goats in Zambia. We found that Plasmodium is readily detectable from water buffalo in these countries, indicating that buffalo Plasmodium is distributed in a wider region than India, which is the only area in which buffalo Plasmodium has been reported. Two types (I and II) of Plasmodium sequences were identified from water buffalo and a third type (III) was isolated from goat. Morphology of the parasite was confirmed in Giemsa-reagent stained blood smears for the Type I sample. Complete mitochondrial DNA sequences were isolated and used to infer a phylogeny in which ungulate malaria parasites form a monophyletic clade within the Haemosporida, and branch prior to the clade containing bird, lizard and other mammalian Plasmodium. Thus it is likely that host switching of Plasmodium from birds to mammals occurred multiple times, with a switch to ungulates independently from other mammalian Plasmodium.