The bacterial aerobic respiratory chain has a terminal oxidase of the heme-copper oxidase superfamily, comprised of cytochrome c oxidase (COX) and ubiquinol oxidase (UOX); UOX evolved from COX. Acetobacter pasteurianus, an α-Proteobacterial acetic acid bacterium (AAB), produces UOX but not COX, although it has a partial COX gene cluster, ctaBD and ctaA, in addition to the UOX operon cyaBACD. We expressed ctaB and ctaA genes of A. pasteurianus in Escherichia coli and demonstrated their function as heme O and heme A synthases. We also found that the absence of ctaD function is likely due to accumulated mutations. These COX genes are closely related to other α-Proteobacterial COX proteins. However, the UOX operons of AAB are closely related to those of the β/γ-Proteobacteria (γ-type UOX), distinct from the α/β-Proteobacterial proteins (α-type UOX), but different from the other γ-type UOX proteins by the absence of the cyoE heme O synthase. Thus, we suggest that A. pasteurianus has a functional γ-type UOX but has lost the COX genes, with the exception of ctaB and ctaA, which supply the heme O and A moieties for UOX. Our results suggest that, in AAB, COX was replaced by β/γ-Proteobacterial UOX via horizontal gene transfer, while the COX genes, except for the heme O/A synthase genes, were lost.