Phosphonate is a commonly used corrosion and scale inhibitor for a circulating cooling water (CCW) system. Its discharge could cause eutrophication of receiving waters. The iron–carbon (Fe/C) micro-electrolysis technology was used to degrade and remove phosphonate from discharged CCW. The influences of initial pH, Fe/C ratio (FCR) and temperature on phosphonate removal were investigated in a series of batch tests and optimized by response surface methodology. The quadratic model of phosphonate removal was obtained with satisfactory degrees of fitness. The optimum conditions with total phosphorus removal efficiency of 95% were obtained at pH 7.0, FCR of 1.25, and temperature of 45 °C. The phosphonate removal mechanisms were also studied. Phosphonate removal occurred predominantly via two consecutive reactive phases: the degradation of phosphonate complexes (Ca–phosphonate) and the precipitation of Fe/C micro-electrolysis products (PO43−, Ca2+ and Fe3+).