Rechargeable Na-ion batteries (NIBs) are attractive large-scale energy storage systems compared to Li-ion batteries due to the substantial reserve and low cost of sodium resources. The recent rapid development of NIBs will no doubt accelerate the commercialization process. As one of the indispensable components in current battery systems, organic liquid electrolytes are widely used for their high ionic conductivity and good wettability, but the low thermal stability, especially the easy flammability and leakage make them at risk of safety issues. The booming solid-state batteries with solid-state electrolytes (SSEs) show promise as alternatives to organic liquid systems due to their improved safety and higher energy density. However, several challenges including low ionic conductivity, poor wettability, low stability/incompatibility between electrodes and electrolytes, etc., may degrade performance, hindering the development of practical applications. In this review, an overview of Na-ion SSEs is first outlined according to the classification of solid polymer electrolytes, composite polymer electrolytes, inorganic solid electrolytes, etc. Furthermore, the current challenges and critical perspectives for the potential development of solid-state sodium batteries are discussed in detail.