Nanocatalysts are frequently connected to magnetic nanoparticles. These composites are easy to be retrieved from the reaction system under a magnetic field because of their magnetic properties. Magnetic separation is particularly promising in industry since it can solve many issues present in filtration, centrifugation, or gravitation separation. Herein, a facile method to prepare bismuth and Fe3O4 nanoparticles loaded on reduced graphene oxide magnetic hybrids (Bi-Fe3O4@RGO) using soluble starch as a dispersant is demonstrated. The magnetic Fe3O4 nanoparticles were synthesized by the co-precipitation of Fe2+ and Fe3+ ions, and Bi nanoparticles were fabricated by the redox reactions between sodium borohydride and ammonium bismuth citrate in the presence of soluble starch. Transmission electron microscopy images demonstrate that the average diameter of the Fe3O4 nanoparticles is about 5 nm and the diameters of Bi nanoparticles range from 10 to 20 nm. The magnetic Bi-Fe3O4@RGO hybrids exhibit high catalytic activity in the reduction of 4-nitrophenol (4-NP) to 4-aminophenol (4-AP) by NaBH4 with a first-order rate constant (K) of 0.00808 s−1 and is magnetically recyclable for at least five cycles. This strategy provides an efficient and recyclable catalyst for the use in environmental protection applications.