We developed a strategy for coupling hollow Fe3O4–Fe nanoparticles with graphene sheets for high-performance electromagnetic wave absorbing material. The hollow Fe3O4–Fe nanoparticles with average diameter and shell thickness of 20 and 8 nm, respectively, were uniformly anchored on the graphene sheets without obvious aggregation. The minimal reflection loss RL values of the composite could reach −30 dB at the absorber thickness ranging from 2.0 to 5.0 mm, greatly superior to the solid Fe3O4–Fe/G composite and most magnetic EM wave absorbing materials recently reported. Moreover, the addition amount of the composite into paraffin matrix was only 18 wt %.