To prevent eutrophication of surface water, phosphate needs to be removed from sewage. Iron (Fe) dosing is commonly used to achieve this goal either as the main strategy or in support of biological removal. Vivianite (Fe(II)3(PO4)2 * 8H2O) plays a crucial role in capturing the phosphate, and if enough iron is present in the sludge after anaerobic digestion, 70–90% of total phosphorus (P) can be bound in vivianite. Based on its paramagnetism and inspired by technologies used in the mining industry, a magnetic separation procedure has been developed. Two digested sludges from sewage treatment plants using Chemical Phosphorus Removal were processed with a lab-scale Jones magnetic separator with an emphasis on the characterization of the recovered vivianite and the P-rich caustic solution. The recovered fractions were analyzed with various analytical techniques (e.g., ICP-OES, TG-DSC-MS, XRD and Mössbauer spectroscopy). The magnetic separation showed a concentration factor for phosphorus and iron of 2–3. The separated fractions consist of 52–62% of vivianite, 20% of organic matter, less than 10% of quartz and a small quantity of siderite. More than 80% of the P in the recovered vivianite mixture can be released and thus recovered via an alkaline treatment while the resulting iron oxide has the potential to be reused. Moreover, the trace elements in the P-rich caustic solution meet the future legislation for recovered phosphorus salts and are comparable to the usual content in Phosphate rock. The efficiency of the magnetic separation and the advantages of its implementation in WWTP are also discussed in this paper.