Considering the increasing interest in the use of graphene-based materials for energy conversion and storage applications, we have performed a DFT study of Na interaction with doped graphene, both in non-oxidized and oxidized forms. Oxidation seems to play the crucial role when it comes to the interaction of doped graphene materials with sodium. The dopants act as attractors of OH groups, making the material prone to oxidation, and therefore altering its affinity towards Na. In some cases, this can result in hydroxide or water formation − an irreversible change lethal for battery performance. Our results suggest that one should carefully control the oxidation level of doped graphene-based materials if they are to be used as sodium battery electrode materials as the optimal oxidation level depends on the dopant type.