Solid electrolytes are important materials with a wide range of technological applications. This work reports the crystal structure and electrical properties of a new solid electrolyte Na9Al(MoO4)6. The monoclinic Na9Al(MoO4)6 consists of isolated polyhedral [Al(MoO4)6]9- clusters composed of a central AlO6 octahedron sharing vertices with six MoO4 tetrahedra to form a three-dimensional framework. The AlO6 octahedron also shares edges with one Na1O6 octahedron and two Na2O6 octahedra. Na3-Na5 atoms are located in the framework cavities. The structure is related to that of sodium ion conductor II-Na3Fe2(AsO4)3. High-temperature conductivity measurements revealed that the conductivity (σ) of Na9Al(MoO4)6 at 803 K equals 1.63 × 10-2 S cm-1. The temperature behavior of the 23Na and 27Al nuclear magnetic resonance spectra and the spin-lattice relaxation rates of the 23Na nuclei indicate the presence of fast Na+ ion diffusion in the studied compound. At T<490 K, diffusion occurs by means of Na+ ion jumps exclusively through the sublattice of Na3-Na5 positions, whereas Na1 and Na2 become involved in the diffusion processes (through chemical exchange with the Na3-Na5 sublattice) only at higher temperatures.