The H2 production potential of [FeFe]-hydrogenase, a hydrogen-producing enzyme from green algae, is reported to be promising for economical and large-scale production of H2 as an alternative source of renewable energy. The production of hydrogen takes place at the catalytic center buried in the enzyme core. Unfortunately, binding of O2 to the catalytic center of the enzyme irreversibly inactivates it, essentially blocking hydrogen production. Therefore, a better understanding of the mechanism of O2 entry/exit is necessary to develop strategies for designing oxygen-tolerant enzymes. In this work, we investigated the pathways and diffusion channels of O2 gas in this hydrogenase. Through exhaustive mapping of oxygen-diffusion channels, we computed a full thermodynamic map of preferred binding locations of O2 gas within the enzyme interior, which showed that O2 can enter and exit the enzyme through multiple pathways along which are key residues that are known to perturb rates of O2 binding. The global minimum in the free-energy landscape is located near the H-cluster, a key metallic center within the enzyme. Along O2 diffusion channels, we further identified several residues that could be potential candidates for mutations to increase the oxygen tolerance of [FeFe]-hydrogenase.