Phosphonates are an important type of phosphorus-containing compounds and have possible eutrophication potential. Therefore, the removal of phosphonates from waste streams is as important as orthophosphate. Herein, we achieved simultaneously removal and recovery of phosphorus from nitrilotris (methylene phosphonic acid) (NTMP) using an electrochemical cell. It was found that the C–N and C–P bonds of NTMP were cleaved at the anode, leading to the formation of orthophosphate and formic acid. Meanwhile, the converted orthophosphate reacted with coexisting calcium ions and precipitated on the cathode as recoverable calcium phosphate solids, due to an electrochemically induced high pH region near the cathode. Electrochemical removal of NTMP (30 mg/L) was more efficient when dosed to effluent of a wastewater treatment plant (89% in 24 h) than dosed to synthetic solutions of 1.0 mM Ca and 50 mM Na2SO4 (43% in 168 h) while applying a current density of 28 A/m2 and using a Pt anode and Ti cathode. The higher removal efficiency of NTMP in real waste water is due to the presence of chloride ions, which resulted in anodic formation of chlorine. This study establishes a one-step approach for simultaneously phosphorus removal and recovery of calcium phosphate from non-orthophosphates.