Using first-principles simulations, we predict a high-performance solid electrolyte with composition Na10GeP2S12 for use in sodium–sulfur (Na–S) batteries. The thermodynamic stability of its structure is established through determination of decomposition reaction energies and phonons, while Na-ionic conductivity is obtained using ab initio molecular dynamics at elevated temperatures. Our estimate of the room-temperature (RT) conductivity is 4.7 × 10−3 S cm−1, which is slightly higher than those of other superionic solid electrolytes such as β″-alumina and Na3Zr2Si2PO12, currently used in practical high-temperature Na–S batteries. Activation energy obtained from the Arrhenius plot (in the range 800–1400 K) is 0.2 eV, which is slightly lower than the typical values exhibited by other ceramic conductors (0.25–1 V) (Hueso et al.,Energy Environ. Sci., 2013, 6, 734). We show that soft Na–S phonon modes are responsible for its thermodynamic stability and the lower activation barrier for diffusion of Na-ions. Finally, the calculated electronic bandgap of 2.7 eV (a wide electrochemical window) augurs well for its safe use in sodium batteries. Opening up a possibility for realizing RT operation of Na–S batteries, our prediction of a new phase in the Na–Ge–P–S system will stimulate experimental studies of the material.