Intermetallic compounds made of alkali metals and gold have intriguing electronic and structural properties that have not been extensively explored. We perform a systematic study of the phase diagram of one binary system belonging to this family, namely Na_xAu_1−x, using the ab initio minima hopping structural prediction method. We discover that the most stable composition is NaAu₂, in agreement with available experimental data. We also confirm the crystal structures of NaAu₂ and Na₂Au, that were fully characterized in experiments, and identify a candidate ground-state structure for the experimental stoichiometry NaAu. Moreover, we obtain three other stoichiometries, namely Na₃Au₂, Na₃Au and Na₅Au, that could be thermodynamically stable. We do not find any evidence for the existence of the experimentally proposed composition NaAu₅. Finally, we perform phonon calculations to check the dynamical stability of all reported phases and we simulate x-ray diffraction spectra for comparison with future experimental data.