Advanced ionic conductors are crucial for a large variety of contemporary technologies spanning solid state ion batteries, fuel cells, gas sensors, water desalination, etc. In this work, we report on a new member of KTiOPO4-structured materials, NaGaPO4F, with sodium-ion conductivity. NaGaPO4F has been obtained for the first time via a facile two-step synthesis consisting of a hydrothermal preparation of an ammonia-based precursor, NH4GaPO4F, followed by an ion exchange reaction with NaNO3. Its crystal structure was precisely refined using a combination of synchrotron X-ray powder diffraction and electron diffraction tomography. The material is thermally stable upon 450 °C showing no significant structural transformations or degradation but only a ∼1% cell volume expansion. Na-ion mobility in NaGaPO4F was investigated by a joint experimental and computational approach comprising solid-state nuclear magnetic resonance (NMR) and density functional theory (DFT). DFT and bond-valence site energy (BVSE) calculations reveal 3D diffusion of sodium in the [GaPO4F] framework with migration barriers amounting to 0.22 and 0.44 eV, respectively, while NMR yields 0.3-0.5 eV that, being coupled with a calculated bandgap of ∼4.25 eV, makes NaGaPO4F a promising fast Na-ion conductor.