This review focuses on the type A cytochrome c oxidases (CcO), which are found in all mitochondria and also in several aerobic bacteria. CcO catalyzes the respiratory reduction of dioxygen (O2) to water by an intriguing mechanism, the details of which are fairly well understood today as a result of research for over four decades. Perhaps even more intriguingly, the membrane-bound CcO couples the O2 reduction chemistry to translocation of protons across the membrane, thus contributing to generation of the electrochemical proton gradient that is used to drive the synthesis of ATP as catalyzed by the rotary ATP synthase in the same membrane. After reviewing the structure of the core subunits of CcO, the active site, and the transfer paths of electrons, protons, oxygen, and water, we describe the states of the catalytic cycle and point out the few remaining uncertainties. Finally, we discuss the mechanism of proton translocation and the controversies in that area that still prevail.