Electronic structures of doped NaTaO3 compounds are of significant interest to visible light photocatalysis. This work involves the study of the band gap, band edge potentials, and thermodynamic stability of certain mono-doped and co-doped NaTaO3 systems, using DFT-PBE as well as hybrid (PBE0) functional calculations. Doping of certain non-magnetic cations (Ti, V, Cu, Zn, W, In, Sn, Sb, Ce, and La), certain anions (N, C, and I), and certain co-dopant pairs (W–Ti, W–Ce, N–I, N–W, La–C, Pb–I, and Cu–Sn) is investigated. Our calculations suggest that substitutional doping of Cu at the Ta site, Cu at the Na site, and C at the O site narrows the band gap of NaTaO3 to 2.3, 2.8, and 2.1 eV, respectively, inducing visible light absorption. Additionally, passivated co-doping of Pb–I and N–W narrows the band gap of NaTaO3 to the visible region, while maintaining the band potentials at favorable positions. Hybrid density of states (DOS) accurately describe the effective band potentials and the location of mid-gap states, which shed light on the possible mechanism of photoexcitation in relation to the photocatalysis reactions. Furthermore, the thermodynamic stability of the doped systems and defect pair binding energies of co-doped systems are discussed in detail. The present results provide useful insights into designing new photocatalysts based on NaTaO3.