To address the issues of eutrophication and the potential risk of phosphorus (P) shortage, it is essential to remove and recover P from P-containing streams to close this nutrient cycle. Electrochemical induced calcium phosphate (CaP) precipitation was shown to be an efficient method for P recovery. However, the influence of natural organic matter (NOM) is not known for this treatment. In this paper, the behavior of NOM and its effect on CaP precipitation was studied. In contrast to studies where NOM hindered CaP precipitation, results show that the interaction of NOM with CaP improves the removal of P, independent of the types of NOM. The P removal at the average increased from 43.8 ± 4.9% to 58.5 ± 1.2% in the presence of 1.0 mg L−1 NOM. Based on the yellow color of the CaP product, NOM is co-precipitated. The bulk solution pH with and without buffers has totally different effects on the precipitation process. Without buffer, CaP precipitates on the cathode surface in a wide pH range (pH 4.0–10.0). However, the precipitation process is completely inhibited when the bulk solution is buffered at pH 4.0 and 6.0. This is probably due to neutralization of OH− by the buffers. Regardless of the presence or absence of NOM and solution pH, the recovered products are mainly amorphous CaP unless the electrolysis time was increased to seven days with 4.0 A m−2, in which crystalline CaP formed. These findings advance our understanding on the interaction of Ca, P and NOM species for the application of electrochemical method for P recovery from real wastewater.