Some ciliates live anaerobically and lack mitochondria, but possess hydrogenosomes: organelles that contain hydrogenase and produce hydrogen. The origin of hydrogenosomes has been explained by two competing hypotheses: (i) they are biochemically modified mitochondria; or (ii) they are derived from endosymbiotic association(s) of ciliates and anaerobic eubacteria that possessed the hydrogenosome biochemistry. Phylogenetic analyses of representative aerobic, and anaerobic hydrogenosomal ciliates using host nuclear SSU rDNA sequences indicate a minimum of three, but more likely four, separate origins of hydrogenosomes. Whereas this does not refute either hypothesis, the implausibility of multiple convergent endosymbioses gives further support to the view that hydrogenosomes in ciliates derive from an existing organelle, which ultrastructural evidence suggests is the mitochondrion. Our results indicate a considerable potential for physiological-biochemical plasticity among a group of predominantly aerobic eucaryotes, and provide a phylogenetic framework to further refine and test hypotheses of the origins of the hydrogenosomal enzymes.