The synthesis of langbeinite-type phosphates with small cations such as Li+ or Na+via a high-temperature solid-state reaction is a challenging task due to the predominant formation of a related NaSICON-type phase. This work reports on the synthesis route, crystal structure, thermal behavior, and Na-conductive properties of the langbeinite-type NaZr2(PO4)3 prepared by a mechanochemically activated ion-exchange reaction between hydrothermally prepared NH4Zr2(PO4)3 and NaNO3. The crystal structure of NaZr2(PO4)3 is refined based on X-ray diffraction data and validated by Fourier-transformed infrared spectroscopy. NaZr2(PO4)3 is found to be stable up to 730 °C, undergoing a transformation into the NaSICON phase with further heating. Notably, in the 25-500 °C range, the material shows negative thermal expansion. The Na+ conductivity within the range of 50-225 °C amounts to 1.7 × 10-8 S cm-1 at 50 °C and 1 × 10-6 S cm-1 at 225 °C with an activation energy of 0.44 eV, accompanied by a sufficiently low (∼10-12 S cm-1) electronic conductivity. The bandgap of 4.44 eV and the electrochemical stability window covering the 1.39-4.18 V vs. Na/Na+ range are calculated using density functional theory. The obtained results open up opportunities for designing langbeinite-structured phosphates as potential solid electrolytes for Na-ion batteries.