Trypanosomes (genus Trypanosoma) are widespread blood parasites of vertebrates, usually transmitted by arthropod or leech vectors. Most trypanosomes have lifecycles that alternate between a vertebrate host, where they exist in the bloodstream, and an invertebrate host, where they develop in the alimentary tract. This raises the question of whether one type of host has had greater influence on the evolution of the genus. Working from the generally accepted view that trypanosomes are monophyletic, here we examine relationships between trypanosomes using phylogenies based on the genes for the small subunit ribosomal RNA (SSU rRNA) and the glycosomal glyceraldehyde phosphate dehydrogenase (gGAPDH). New analysis of a combined dataset of both these genes provides strong support for many known clades of trypanosomes. It also resolves the deepest split within the genus between the Aquatic clade, which mainly contains trypanosomes of aquatic and amphibious vertebrates, and a clade of trypanosomes from terrestrial vertebrates. There is also strengthened support for two deep clades, one comprising a wide selection of mammalian trypanosomes and a tsetse fly-transmitted reptilian trypanosome, and the other combining two bird trypanosome subclades. Considering the vertebrate and invertebrate hosts of each clade, it is apparent that co-speciation played little role in trypanosome evolution. However most clades are associated with a type of vertebrate or invertebrate host, or both, indicating that 'host fitting' has been the principal mechanism for evolution of trypanosomes.