Using classical electrostatic calculations (Popovic, D. M.; Stuchebrukhov, A. A. J. Am. Chem. Soc. 2004, 126, 1858), earlier we examined the dependence of the protonation state of bovine cytochrome c oxidase (CcO) on its redox state. Based on these calculations, we have proposed a model of CcO proton pumping that involves His291, one of the CUB histidine ligands, which was found to respond to redox changes of the enzyme Fe-a3-Cu-B catalytic center (Popovic, D. M.; Stuchebrukhov, A. A. FEBS Lett. 2004, 566, 126). In this work, we employ combined density functional and continuum electrostatic calculations to evaluate the pK(a) values of His291 and Glu242, two key residues of the model. The pK(a) values are calculated for different redox states of the enzyme, and the influence of different factors on the pK(a)'s is analyzed in detail. The calculated pK(a) values of Glu242 are between 9.4 and 12.0, depending on the redox state of the protein, which is in excellent agreement with recent experimental measurements. Assuming the reduced state of heme a(3), His291 of the oxidized Cu-B center possesses a pK(a) between 2.1 and 4.0, while His291 of the reduced Cu-B center has a pK(a) above 17. The obtained results support the proposal that the His291 ligand of the Cu-B center in CcO is a proton pump element.