Metal-air batteries have higher theoretical specific energies than existing rechargeable batteries including Li-ion batteries. Among metal-air batteries, the Na-O2 battery has gained much attention due to its low discharge/charge overpotentials (∼100 mV) at relatively high current densities (0.2 mA/cm2), high electrical energy efficiency (90%), high theoretical energy density, and low cost. However, there is no information reported regarding the effect of CO2 contamination in non-aqueous Na-air batteries. Density functional theory has, here, been applied to study the effect of low concentrations of CO2 contamination on NaO2 and Na2O2 growth/depletion reaction pathways and overpotentials. This was done on step surfaces of discharge products in non-aqueous Na-air batteries. Adsorption energies of CO2 at various nucleation sites for both step surfaces were determined, and results revealed that CO2 preferentially binds at the step valley sites of (001) NaO2 and 11¯00 Na2O2 surfaces with binding energies of -0.65 eV and -2.67 eV, respectively. CO2 blocks the step nucleation site and influences the reaction pathways and overpotentials due to carbonate formation. The discharge electrochemical overpotential increases remarkably from 0.14 V to 0.30 V and from 0.69 V to 1.26 V for NaO2 and Na2O2 surfaces, respectively. CO2 contamination is thus drastically impeding the growth/depletion mechanism pathways and increases the overpotentials of the surface reaction mechanism, hampering the performance of the battery. Avoiding CO2 contamination from intake of gas and electrolyte decomposition is thus critical in development of Na-air batteries.