While phosphotellurite glasses have superior properties over SiO2-based glasses for many applications in optoelectronics and photonic devices, their high hydroxyl content limits their use in the mid-infrared range. This drawback can be overcome by fluoride addition to the formulation. In this work, we report the preparation, optical, and structural characterization of new glasses in the ternary system TeO2-xNaF-NaPO3 having the compositions 0.8TeO2-0.2[xNaF-(1 - x)NaPO3] and 0.6TeO2-0.4[xNaF-(1 - x)NaPO3] (0 ≤ x ≤ 1) obtained by the traditional melt-quenching method and labeled as T8NNx and T6NNx, respectively. Differential scanning calorimetry (DSC) reveals high thermal stability against crystallization, with Tx-Tg varying from 80 to 130 °C, depending on fluoride/phosphate ratios. Raman spectroscopy suggests that the network connectivity increases with increasing phosphate concentration. 125Te, 23Na, 31P, and 19F NMR spectroscopy provides detailed structural information about Te-O-P, Te-F, Te-O-Te, P-O-P, and P-F linkages and the charge compensation mechanism for the sodium ions. The present study is the first comprehensive structural characterization of a fluorophosphotellurite glass system.