The aim of this work was to use phosphogypsum (FY) waste in a sustainable paving practice involving the production of FY-foamed bitumen for road applications. For this proposal, three FY types coming from different fertilizer industries and a reference natural gypsum were used as foaming agents (10 wt%), including a small quantity of sulfuric acid (0.5 wt%) in the foamed bitumen formulation. The foaming properties and the rheological characterization of their corresponding binder residues were conducted by a distance laser sensor and by dynamic shear rheology, respectively. In addition, a physicochemical characterization of the used materials was carried out in order to evaluate their role in the final product. Knowing that FY is a Naturally Occurring Radioactive Material (NORM) waste, a comprehensive radioactive characterization, by both alpha and gamma spectrometry, and an environmental evaluation, by a Dynamic Surface Leaching Test (DSLT), were performed to comply with the EU radiological regulation of NORM materials for building materials. In conclusion, FY-foamed bitumen displayed enhanced engineering properties compared to that prepared with the reference natural gypsum, satisfying the radioactive and environmental specifications established according to the EU regulations.