Carbon materials have been widely used to form air cathodes for non-aqueous sodium-oxygen (NaO2) batteries due to their large specific surface area, high conductivity and low cost. However, the effect of carbon structures at the atomic level remains poorly understood. In this work, a first-principles study is conducted to investigate how representative carbon structures, including graphite (0001) surface, point defects and fractured edge, influence the discharge and charge processes of non-aqueous NaO2 batteries. It is found that the single vacancy (SV) defect has the largest adsorption energy (5.81 eV) to NaO2 molecule among the structures studied, even larger than that of the NaO2 molecule on NaO2 crystal (2.81 eV). Such high adsorption energy is attributed to two factors: the dangling atoms in SV defects decrease the distance from NaO2 molecules, and the attachment through oxygen atoms increases the electrons transfer. The findings suggest that SV defects can act as the nucleation sites for NaO2 in the discharge process, and increasing the number of SV defects can facilitate the uniform formation of small-sized particles. The uniformly distributed discharge products lower the possibility for pore clogging, leading to an increased discharge capacity and improved cyclability for non-aqueous NaO2 batteries.