Magnetic barium phosphate nanoflakes with embedded iron oxide nanoparticles, Fe3O4@Ba3(PO4)2 (denoted FBP), were prepared through a facile and inexpensive two-step process. FBP was used to purify water heavily contaminated with E. coli (initial concentration of 5 × 108 CFU mL-1). FBP exhibited high removal efficiency (97%) within 30 min at 25 °C and pH 6. We investigated the effects of factors such as pH, ionic strength, co-existing anions, temperature, contact time, material dosage, and initial concentration of bacterial suspension, and developed optimized treatment conditions. The negligible effect of solution ionic strength on bacterial removal efficiency of FBP indicates its potential for microbial control even in high salinity water. Importantly, FBP can maintain a high bacterial removal efficiency of 87% after being reused for five cycles. FBP's magnetic properties allow an easy recovery from water. Several types of forces and mechanisms are thought to be involved in the bacterial removal process by FBP: electrostatic interactions, adhesion to FBP's planar surface, flocculation by polyvalent cations on FBP's surface, oxidation sterilization from Fe3O4 in FBP, irreversible cell structural damage by FBP's edges and corners, and magnetic aggregation under a magnetic field. Thus, FBP is a promising material for effectively treating water with high microbial contamination.