The genomes of Trypanosoma brucei, Trypanosoma cruzi and Leishmania major have been sequenced, but the phylogenetic relationships of these three protozoa remain uncertain. We have constructed trypanosomatid phylogenies based on genes for glycosomal glyceraldehyde phosphate dehydrogenase (gGAPDH) and small subunit ribosomal RNA (SSU rRNA). Trees based on gGAPDH nucleotide and amino acid sequences (51 taxa) robustly support monophyly of genus Trypanosoma, which is revealed to be a relatively late-evolving lineage of the family Trypanosomatidae. Other trypanosomatids, including genus Leishmania, branch paraphyletically at the base of the trypanosome clade. On the other hand, analysis of the SSU rRNA gene data produced equivocal results, as trees either robustly support or reject monophyly depending on the range of taxa included in the alignment. We conclude that the SSU rRNA gene is not a reliable marker for inferring deep level trypanosome phylogeny. The gGAPDH results support the hypothesis that trypanosomes evolved from an ancestral insect parasite, which adapted to a vertebrate/insect transmission cycle. This implies that the switch from terrestrial insect to aquatic leech vectors for fish and some amphibian trypanosomes was secondary. We conclude that the three sequenced pathogens, T. brucei, T. cruzi and L. major, are only distantly related and have distinct evolutionary histories.