Cytochrome c oxidases (Ccoxs) are the terminal enzymes of the respiratory chain in mitochondria and most bacteria. These enzymes couple dioxygen (O2) reduction to the generation of a transmembrane electrochemical proton gradient. Despite decades of research and the availability of a large amount of structural and biochemical data available for the A-type Ccox family, little is known about the channel(s) used by O2 to travel from the solvent/membrane to the heme a3-CuB binuclear center (BNC). Moreover, the identification of all possible O2 channels as well as the atomic details of O2 diffusion is essential for the understanding of the working mechanisms of the A-type Ccox. In this work, we determined the O2 distribution within Ccox from Rhodobacter sphaeroides, in the fully reduced state, in order to identify and characterize all the putative O2 channels leading towards the BNC. For that, we use an integrated strategy combining atomistic molecular dynamics (MD) simulations (with and without explicit O2 molecules) and implicit ligand sampling (ILS) calculations. Based on the 3D free energy map for O2 inside Ccox, three channels were identified, all starting in the membrane hydrophobic region and connecting the surface of the protein to the BNC. One of these channels corresponds to the pathway inferred from the X-ray data available, whereas the other two are alternative routes for O2 to reach the BNC. Both alternative O2 channels start in the membrane spanning region and terminate close to Y288I. These channels are a combination of multiple transiently interconnected hydrophobic cavities, whose opening and closure is regulated by the thermal fluctuations of the lining residues. Furthermore, our results show that, in this Ccox, the most likely (energetically preferred) routes for O2 to reach the BNC are the alternative channels, rather than the X-ray inferred pathway.