The crystal structure of bovine cytochrome c oxidase (CcO) shows a sodium ion (Na+) bound to the surface of subunit I. Changes in the absorption spectrum of heme a caused by calcium ions (Ca2+) are detected as small red shifts, and inhibition of enzymatic activity under low turnover conditions is observed by addition of Ca2+ in a competitive manner with Na+. In this study, we determined the crystal structure of Ca2+-bound bovine CcO in the oxidized and reduced states at 1.7 Å resolution. Although Ca2+ and Na+ bound to the same site of oxidized and reduced CcO, they led to different coordination geometries. Replacement of Na+ with Ca2+ caused a small structural change in the loop segments near the heme a propionate and formyl groups, resulting in spectral changes in heme a. Redox-coupled structural changes observed in the Ca2+-bound form were the same as those previously observed in the Na+-bound form, suggesting that binding of Ca2+ does not severely affect enzymatic function, which depends on these structural changes. The relation between the Ca2+ binding and the inhibitory effect during slow turnover, as well as the possible role of bound Ca2+ are discussed.