Coordination polymers (CPs) often suffer from poor hydrolytic and chemical stability, limiting their use in water remediation. Herein, we report a highly robust, amorphous CP synthesized from Zr4+ and phytic acid, a natural source of phosphorus in plants and seeds. The CP, which features stable Zr-O-P bonds that resist degradation even in 10 M HCl and HNO3, forms a micro- and mesoporous network under mild reaction conditions in water. The material consists of mononuclear ZrO6 units bridged by phosphate groups. Zr-Phytate exhibits excellent Pb2+ removal performance, maintaining high efficiency even in the presence of excess competing ions. Pair Distribution Function (PDF) analysis and solid-state NMR (ssNMR) 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.