Cytochrome c oxidases (CcOs) are the terminal enzymes in energy-converting chains of microorganisms, where they reduce oxygen into water. Their affinity for O2 makes them attractive biocatalysts for technological devices in which O2 concentration is limited, but the high overpotentials they display on electrodes severely limit their applicative use. Here, the CcO of the acidophilic bacterium Acidithiobacillus ferrooxidans is studied on various carbon materials by direct protein electrochemistry and mediated one with redox mediators either diffusing or co-immobilized at the electrode surface. The entrapment of the CcO in a network of hydrophobic carbon nanofibers permits a direct electrochemical communication between the enzyme and the electrode. We demonstrate that the CcO displays a μM affinity for O2 and reduces O2 at exceptionally high electrode potentials in the range of +700 to +540 mV vs NHE over a pH range of 4-6. The kinetics of interactions between the enzyme and its physiological partners are fully quantified. Based on these results, an electron transfer pathway allowing O2 reduction in the acidic metabolic chain is proposed.