Coordination polymers (CPs) often suffer from poor hydrolytic and chemical stability, limiting their use in water remediation. We report a highly robust, amorphous coordination polymer synthesized from Zr⁴⁺ and bio-available phytic acid, featuring stable Zr–O–P bonds that resist degradation even in 10 M HCl and HNO₃. The material forms a micro-mesoporous network under mild conditions in water and consists of mononuclear ZrO₆ units bridged by phosphate groups. Zr-Phytate exhibits excellent Pb²⁺ removal performance, maintaining high efficiency even in the presence of excess competing ions. Pair Distribution Function (PDF) analysis and solid-state NMR (ssNMR) spectroscopy provide insight into the coordination environment of the Zr-phosphate centers and the mechanism of lead complexation. The exceptional chemical durability of Zr-Phytate allows efficient regeneration using 1 M HCl, with no detectable leaching of Zr or phytic acid and no loss of structural integrity over multiple cycles. Compared to commercial ion-exchange resins, Zr-Phytate offers superior selectivity and reusability. This work demonstrates the importance of designing stable coordination polymers and highlights the promise of zirconium-phosphate networks for applications in water remediation.