Complete genome sequences for many oxygen-respiring mitochondria, as well as for some bacteria, leave no doubt that mitochondria are descendants of alpha-proteobacteria, a finding for which the endosymbiont hypothesis can easily account. Yet a wealth of data indicate that mitochondria and hydrogenosomes - the ATP-producing organelles of many anaerobic protists - share a common ancestry, a finding that traditional formulations of the endosymbiont hypothesis less readily accommodates. Available evidence suggests that a more in-depth understanding of the origins of eukaryotes and their organelles will hinge upon data from the genomes of protists that synthesize ATP without the need for oxygen.