Polar perovskite oxide surfaces are subject to structural reconstruction as a possible stabilisation mechanism, which changes the surface structure and hence the surface chemistry. To investigate this effect, we study the oxygen evolution reaction (OER) on two possible reconstructed (001) surfaces of NaTaO₃, by means of density functional theory (DFT) calculations and compare them with the non-polar (113) surface of the same material. For the clean surface the reconstruction has a beneficial effect on the catalytic activity, lowering the minimal overpotential from 0.88 V to 0.70 V while also changing the most active reaction site from Na to Ta. Under photocatalytic conditions, the Ta sites are covered by oxygen adsorbates, rendering lattice oxygen sites on the NaO terrace the most active with a very low overpotential of 0.32 V. An alternative reconstructed surface which is stable in contact with water leads to an oxygen coupling mechanism with an overpotential of 0.52 V. Our results show that terraced surface reconstruction enables novel reaction pathways with low overpotentials which did not exist on previously investigated non-polar NaTaO₃ surfaces or on non-polar surfaces of chemically similar materials such as SrTaO₂N.