In this work commercially available Fe3O4 NPs were coated with polyallylamine hydrochloride (PAH) and PAH functionalized with guanidinium groups (PAH–Gu) for investigating the phosphate adsorption properties under alkaline conditions. The coating can be prepared easily and rapidly and results in Fe3O4 NPs with improved properties related to phosphate binding and colloidal stability. At a low initial phosphate concentration (2 mg L−1), the novel Fe3O4@PAH–Gu material was able to remove phosphate rather independently of the pH condition (4.0, 3.6 and 3.7 mg g−1 at pH = 5, 8 and 10, respectively), whereas for the uncoated Fe3O4 NPs the amount of adsorbed phosphate drops by >75% upon changing from acidic to alkaline conditions (0.84 mg g−1 at pH = 10). Under alkaline conditions, the fastest adsorption was observed for Fe3O4@PAH–Gu followed by Fe3O4@PAH and Fe3O4. This can be related to the additional interaction forces due to the presence of primary amine groups (in PAH and PAH–Gu) and Gu groups (in PAH–Gu only) in coatings. Over 80% of the phosphate adsorbed on the novel Fe3O4@PAH–Gu material was successfully desorbed and the coated NPs were re-used over three adsorption/desorption cycles. This work will stimulate the design and preparation of functionalized polyelectrolytes for an extended area of applications, especially for the selective removal of target compounds from wastewater.