Immobilization of Cytochrome c oxidase (CcO) on electrodes makes voltage-driven reduction of oxygen to water possible. Efficient catalytic turnover in CcO/electrode systems is, however, often observed at large overpotentials that cannot be rationalized by the redox properties of the enzyme itself. To understand the structural basis for this observation, CcO was electrostatically adsorbed on amino-functionalized Ag electrodes, and the redox transitions of heme a and a3 were monitored via surface enhanced resonance Raman spectroscopy (SERRS) as a function of applied potential. Under completely anaerobic conditions, the reduction of heme a3 could be seen at potentials close to those measured in solution indicating an intact catalytic center. However, in the immobilized state, a new non-native heme species was observed that exhibited a redox potential much more negative than measured for the native hemes. Analysis of the high and low frequency SERR spectra indicated that this new species is formed from heme a upon axial loss of one histidine ligand. It is concluded that the formation of the non-native heme a species alters the potential-dependent electron supply to the catalytic reaction and, thus, can have a impact on the applicability of this enzyme in biofuel cells.