The progress in the research and development of high temperature sodium batteries suggests that all-solid-state batteries with inorganic or polymer solid electrolytes are promising power sources for a wide range of applications due to their high thermal stability, reliability, long-cycle life and versatile geometries. The electrolytes play a fundamental role in terms of current (power) density, the time stability, and the safety of batteries and, as a result, their continuous improvement and innovation are indeed critical to success. In fact, inorganic solid electrolytes pave the way for improving the cost-effective development of rechargeable sodium batteries. This review describes a state-of-the-art overview of most of the Na+ conductors for use as electrolytes in sodium/sulphur and ZEBRA batteries. The emphasis of this article is on inorganic solid electrolytes, especially, ceramic and glass-ceramic electrolytes as promising alternatives applicable to all solid-state batteries. As part of a continuous effort to find new materials that operate at room temperature and moderate temperatures, NASICON electrolytes will also be considered. Polymer electrolytes based on poly(ethylene oxide) (PEO) are also very suitable for all solid-state batteries. Hence, the review focuses on ion transport based on the observed conductivity, electrolyte preparation, safety and environmental impact.