Trichomonas is a significant protist genus, and includes T. vaginalis, the most prevalent sexually transmitted non-viral infection of humans, and T. gallinae of rock doves (Columba livia), one of the earliest known avian pathogens. New Trichomonas genotypes, including T. vaginalis-like isolates, have been discovered in American columbid hosts, suggesting geographically widespread cryptic diversity of Trichomonas in pigeons and doves. We sampled 319 birds from 22 columbid species in Australia, Papua New Guinea, New Zealand and southern Africa and uncovered 15 novel lineages of Trichomonas, more than doubling the known diversity of this parasite genus and providing evidence for frequent host-switching that eventually gave rise to T. vaginalis in humans. We show that Trichomonas has a columbid origin and likely underwent Miocene expansion out of Australasia. Our chronological topology for Trichomonas is calibrated on the evolution of a host phenotypic trait associated with ecological entrapment of the most basal extant lineage of Trichomonas in Ptilinopus fruit-doves.