The three deepest branching eucaryotic lineages in small subunit ribosomal RNA phylogenies are the amitochondriate Microspora, Metamonada and Parabasala. They are followed by either the Euglenozoa (e.g. Euglena and Trypanosoma) or the Percolozoa as the first mitochondria-containing eucaryotes. To investigate the hypothesis of an even earlier timing of the mitochondrion endosymbiosis we have amplified a partial cpn-60 coding region from the parabasalid Trichomonas vaginalis and the first such sequence from a percolozoan, Naegleria fowleri. Analysis of predicted protein sequences reveals a high degree of sequence similarity ($\geq $ 40%) with a selection of published bacterial and mitochondrial cpn-60s for both taxa. Both sequences were recovered within a strongly supported monophyletic group, otherwise defined by mitochondrial sequences, which systematically clustered with alpha-proteobacteria. These results provide compelling evidence that the ancestor of T. vaginalis once contained the endosymbiont which gave rise to mitochondria, and suggest that this symbiosis probably occurred before the Trichomonas lineage diverged from the main eukaryote trunk. It also makes feasible the published hypothesis that the Trichomonas hydrogenosome might represent a biochemically modified mitochondrion. Analysis of the N. fowleri cpn-60 did not support the hypothesis that the mitochondrion-containing Percolozoa represent an earlier branch in the cpn-60 tree than Trichomonas or Trypanosoma.