The molecular structures of low-lying isomers of anionic and neutral sodium auride clusters have been studied computationally at the second-order Moller-Plesset perturbation theory level using quadruple-zeta basis sets augmented with a double set of polarization functions. The first vertical detachment energies were calculated at the Moller-Plesset level as the energy difference between the cluster anion and the corresponding neutral cluster. The photodetachment energies of higher-lying ionization channels were calculated by adding electronic excitation energies of the neutral clusters to the first vertical detachment energy. The excitation energies were calculated at the linear response approximate coupled-cluster singles and doubles level using the anionic cluster structures. The obtained ionization energies for NaAu-, NaAu2-, NaAu3-, NaAu4-, Na2Au2-, Na2Au3-, Na3Au3-, and Na2Au4- were compared to values deduced from experimental photoelectron spectra. Comparison of the calculated photoelectron spectra for a few energetically low-lying isomers shows that the energetically lowest cluster structures obtained in the calculations do not always correspond to the clusters produced experimentally. Spin-component-scaled second-order Moller-Plesset perturbation theory calculations shift the order of the isomers such that the observed clusters more often correspond to the energetically lowest structure, whereas the spin-component-scaled approach does not improve the photodetachment energies of the sodium aurides. The potential energy surface of the sodium aurides is very soft, with several low-lying isomers requiring an accurate electron correlation treatment. The calculations show that merely the energetic criterion is not a reliable means to identify the structures of the observed sodium auride clusters; other experimental information is needed to ensure a correct assignment of the cluster structures. The cluster structures of nonstoichiometric anionic sodium aurides have been determined by comparing calculated ionization energies for low-lying structures of the anionic clusters with experimental data.