Cytochrome c oxidase (CcO), a redox proton pump, terminates the aerobic respiratory chain by catalyzing the reduction of O2 to water. Various isoforms of CcO enzymes with distinct biochemical properties and different organism distributions have been identified. A-type CcOs are distributed in all three kingdoms of life. B-type CcOs are found only in archaea and bacteria. CcOs rely on efficient pathways for protons, electrons, and O2, connecting their buried heme-copper catalytic site to the surface of the protein. Here, we employed molecular dynamics simulation to probe and characterize pathways for the O2 delivery to CcO's catalytic site using both explicit and implicit ligand sampling methods. A-type (CcO caa3) and B-type (CcO ba3) CcO enzymes from Thermus thermophilus were investigated. While CcO caa3 is constitutively expressed, CcO ba3 is expressed under low oxygen condition, implying possible differences between the two enzymes in their ability and efficiency to recruit O2. Although the characterized O2 pathways exhibit a close similarity between the two enzymes from a structural perspective, O2 dynamics through these pathways is quite different. In CcO ba3, O2 reached the catalytic site rather rapidly, i.e., within a few nanoseconds, while the process was much slower and required several tens of nanoseconds in CcO caa3. In each enzyme, O2 entered the protein and reached the catalytic site via a membrane-accessible hydrophobic channel observed in X-ray structures. While O2 was found to diffuse freely into CcO ba3 through the hydrophobic channel, the O2 pathway in CcO caa3 was constricted by the presence of large aliphatic and aromatic residues. The findings relate the functional and structural adaption of CcO to oxygen-stress conditions.