Development of the technologies for energy storage and conversion requires a search for compounds with high diffusion of alkali and alkaline-earth ions. Here, we present the results of comprehensive studies, including synthesis, powder X-ray diffraction, experiments on impedance and 23Na NMR spectroscopy, as well as ab initio calculations, which were carried out to explore the sodium diffusion in scheelite-like Na5M(MoO4)4 with M = Y, La, Bi, and in related solid solutions Na5-xM1-xZrx(MoO4)4 (0.05 ≤ x ≤ 0.1), which were synthesized for the first time. Our investigations reveal that the Na-ion mobility increases in the sequence Y → La → Bi and with growing x. For Na4.9Bi0.9Zr0.1(MoO4)4 the highest ion conductivity was found: ∼10−4 S/cm at T = 450 °C, which is comparable to that of the NASICON-type molybdates. From the temperature variations of the 23Na NMR spectra and DFT calculations, the mechanism of sodium-ion diffusion was established at the atomic-scale level.