Radioactive fluoride wastes are generated during the operation of molten salt reactors (MSRs) and reprocessing of their spent fuel. Immobilization of these wastes in borosilicate glass is not feasible because of the very low solubility of fluorides in this host. Alternative candidates are thus an active topic of research including phosphate-based glasses, crystalline ceramics, and hybrid glass–ceramic systems. In this study, mixed fluorides were employed as simulated MSRs waste and incorporated into sodium aluminophosphate glass to obtain phosphate-based waste form. These waste forms were characterized by X-ray diffraction, Raman spectroscopy, and scanning electron microscopy. Leaching tests were performed in deionized water using the product consistency test A method. This study demonstrates that up to 20 mol% of simulated radioactive waste can be introduced into the NaAlP glass matrix, and the chemical durability is much better than that of borosilicate. The addition of Fe2O3 in the NaAlP glass matrix results in increases of the chemical durability at the expense of fluoride loading (to 6.4 mol%). Phosphate glass vitrification of radioactive waste containing fluorides is a potential method to treat and dispose of MSR wastes.