We developed a novel slow-release nitrogen fertilizer with the aim of increasing the efficiency of urea use, recycling phosphogypsum, and reducing related pollution. Phosphogypsum was used as a granulating agent and carrier for urea to prepare a novel fertilizer core, which was coated with paraffin wax. Span™ 80 was added to the paraffin to improve the wetting and adhesion between the paraffin coating and the fertilizer core. Paraffin-coated urea particles were prepared as a control sample using this method and their urea-release behavior was investigated. The results showed that less than 35% of urea from the paraffin-coated phosphogypsum-granulated urea was released over 28 days of submersion in water. The urea release was sustained much longer than that of paraffin-coated urea (only 7 days due to the expansion of brittle cracks in the coating). The release patterns of all coated fertilizers followed a logistic model. The release efficiency of paraffin-coated fertilizers could be improved by increasing the particle size of the fertilizer cores and improving adhesion between the paraffin coating and fertilizer core.