Increasing demand for lithium batteries for automotive applications, coupled with the necessity to move to large-scale energy storage systems, is driving a push towards new technologies and has seen Na-ion batteries emerge as a leading alternative to Li-ion. Amongst these, all solid-state configurations represent a promising route to achieving higher energy densities and increased safety. Remaining challenges include the need for Na+ solid electrolytes with the requisite ionic conductivities crucial for use in a solid-state cell. Here, we present the novel Na-rich double perovskite, Na1.5La1.5TeO6. The transport properties, explored at the macroscopic and local level, reveal a low activation energy barrier for Na+ diffusion and great promise for use as an electrolyte for all solid-state Na-batteries.