Phosphate recovery from sewage sludge is essential in a circular economy. Currently, the main focus in centralized municipal wastewater treatment plants (MWTPs) lies on struvite recovery routes, land application of sludge or on technologies that rely on sludge incineration. These routes have several disadvantages. Our study shows that the mineral vivianite, Fe2(PO4)3 × 8H2O, is present in digested sludge and can be the major form of phosphate in the sludge. Thus, we suggest vivianite can be the nucleus for alternative phosphate recovery options. Excess and digested sewage sludge was sampled from full-scale MWTPs and analysed using x-ray diffraction (XRD), conventional scanning electron microscopy with energy dispersive X-ray spectroscopy (SEM-EDX), environmental SEM-EDX (eSEM-EDX) and Mössbauer spectroscopy. Vivianite was observed in all plants where iron was used for phosphate removal. In excess sludge before the anaerobic digestion, ferrous iron dominated the iron pool (≥50%) as shown by Mössbauer spectroscopy. XRD and Mössbauer spectroscopy showed no clear correlation between vivianite bound phosphate versus the iron content in excess sludge. In digested sludge, ferrous iron was the dominant iron form (>85%). Phosphate bound in vivianite increased with the iron content of the digested sludge but levelled off at high iron levels. 70–90% of all phosphate was bound in vivianite in the sludge with the highest iron content (molar Fe:P = 2.5). The quantification of vivianite was difficult and bears some uncertainty probably because of the presence of impure vivianite as indicated by SEM-EDX. eSEM-EDX indicates that the vivianite occurs as relatively small (20–100 μm) but free particles. We envisage very efficient phosphate recovery technologies that separate these particles based on their magnetic properties from the complex sludge matrix.