Cytochrome c oxidase (CcO) reduces oxygen to water and uses the released free energy to pump protons across the membrane. We have used multiscale reactive molecular dynamics simulations to explicitly characterize (with free-energy profiles and calculated rates) the internal proton transport events that enable proton pumping during first steps of oxidation of the fully reduced enzyme. Our results show that proton transport from amino acid residue E286 to both the pump loading site (PLS) and to the binuclear center (BNC) are thermodynamically driven by electron transfer from heme a to the BNC, but that the former (i.e., pumping) is kinetically favored whereas the latter (i.e., transfer of the chemical proton) is rate-limiting. The calculated rates agree with experimental measurements. The backflow of the pumped proton from the PLS to E286 and from E286 to the inside of the membrane is prevented by large free-energy barriers for the backflow reactions. Proton transport from E286 to the PLS through the hydrophobic cavity and from D132 to E286 through the D-channel are found to be strongly coupled to dynamical hydration changes in the corresponding pathways and, importantly, vice versa.