In light of growing concerns about the formation of nitrogen-based disinfection byproducts (N-DBP) and the possible contribution from the use of quaternary-ammonium-containing flocculants, there is growing interest in the alternative use of quaternary phosphonium salts, which have been reported to have a lower DBP formation potential, stronger cationic properties, lower cytotoxicity, and greater stability. In this study, the performance of N-free quaternary-phosphonium-modified starch flocculants (S-BTP), synthesized through a facile one-step method using commercially available raw materials, in the treatment of bacteria-laden waters (E. coli as the model bacteria) was assessed in both jar tests and a bench-scale continuous-flow flocculation–sedimentation–ultrafiltration process. In jar tests, the effects of the cationic degree of substitution (DS) and dosage of the flocculant, solution pH, and presence of model contaminants on treatment performance were studied. One particular flocculant (S-BTP3), with a DS of 19.3%, displayed high removal efficiencies of E. coli, turbidity, and UV254 from water, comparable with those of ammonium-based analogues and conventional alum, via a combination of charge attraction, polymer bridging, and antibacterial effects. S-BTP3 also possessed better bactericidal properties (99.4% of E. coli killed) than alum (41.4% killed) and did not cause the release of intracellular substances into the treated water. In the continuous-flow flocculation–sedimentation–UF tests, S-BTP3 was superior to alum in the flocculation and antibacterial performance, and in mitigating UF membrane fouling. The results have clearly demonstrated the multiple benefits of the use of N-free cationic starch flocculants in water treatment as an alternative to conventional chemicals.