Mitochondria occur as aerobic, facultatively anaerobic, and, in the case of hydrogenosomes, strictly anaerobic forms. This physiological diversity of mitochondrial oxygen requirement is paralleled by that of free-living alpha-proteobacteria, the group of eubacteria from which mitochondria arose, many of which are facultative anaerobes. Although ATP synthesis in mitochondria usually involves the oxidation of reduced carbon compounds, many alpha-proteobacteria and some mitochondria are known to use sulfide (H2S) as an electron donor for the respiratory chain and its associated ATP synthesis. In many eubacteria, the oxidation of sulfide involves the enzyme sulfide:quinone oxidoreductase (SQR). Nuclear-encoded homologs of SQR are found in several eukaryotic genomes. Here we show that eukaryotic SQR genes characterized to date can be traced to a single acquisition from a eubacterial donor in the common ancestor of animals and fungi. Yet, SQR is not a well-conserved protein, and our analyses suggest that the SQR gene has furthermore undergone some lateral transfer among prokaryotes during evolution, leaving the precise eubacterial lineage from which eukaryotes obtained their SQR difficult to discern with phylogenetic methods. Newer geochemical data and microfossil evidence indicate that major phases of early eukaryotic diversification occurred during a period of the Earth's history from 1 to 2 billion years before present in which the subsurface ocean waters contained almost no oxygen but contained high concentrations of sulfide, suggesting that the ability to deal with sulfide was essential for prokaryotes and eukaryotes during that time. Notwithstanding poor resolution in deep SQR phylogeny and lack of a specifically alpha-protebacterial branch for the eukaryotic enzyme on the basis of current lineage sampling, a single eubacterial origin of eukaryotic SQR and the evident need of ancient eukaryotes to deal with sulfide, a process today germane to mitochondrial quinone reduction, are compatible with the view that eukaryotic SQR was an acquisition from the mitochondrial endosymbiont.