Oxygen reducing terminal oxidases differ with respect to their subunit composition, heme groups, operon structure, and affinity for O2. Six families of terminal oxidases are currently recognized, all of which occur in alphaproteobacterial genomes, two of which are also present in mitochondria. Many alphaproteobacteria encode several different terminal oxidases, likely reflecting ecological versatility with respect to oxygen levels. Terminal oxidase evolution likely started with the advent of O2 roughly 2.4 billion years ago and terminal oxidases diversified in the Proterozoic, during which oxygen levels remained low, around the Pasteur point (ca. 2 μM O2). Among the alphaproteobacterial genomes surveyed, those from members of the Rhodospirillaceae reveal the greatest diversity in oxygen reductases. Some harbor all six terminal oxidase types, in addition to many soluble enzymes typical of anaerobic fermentations in mitochondria and hydrogenosomes of eukaryotes. Recent data have it that O2 levels increased to current values (21% v/v or ca. 250 μM) only about 430 million years ago. Ecological adaptation brought forth different lineages of alphaproteobacteria and different lineages of eukaryotes that have undergone evolutionary specialization to high oxygen, low oxygen, and anaerobic habitats. Some have remained facultative anaerobes that are able to generate ATP with or without the help of oxygen and represent physiological links to the ancient proteobacterial lineage at the origin of mitochondria and eukaryotes. Our analysis reveals that the genomes of alphaproteobacteria appear to retain signatures of ancient transitions in aerobic metabolism, findings that are relevant to mitochondrial evolution in eukaryotes as well.