A novel anionic polyelectrolyte poly(4-styrenesulfonic acid-co-maleic acid) sodium (PSSMA) decorated magnetic graphene oxide (MGO@PSSMA) was prepared by a simple and facile one-step solvothermal method in this paper, and used for the removal of heavy metal lead (Pb(II)) and copper ions (Cu(II)) from aqueous solution. The prepared MGO@PSSMA was characterized by FTIR, SEM, TEM, VSM and DLS. Batch adsorption studies were performed to investigate the effects of solution pH, adsorption time and initial solution concentration on the adsorption of Pb(II) and Cu(II) onto MGO@PSSMA and MGO without modifying with PSSMA, and the adsorption isotherms, kinetics and mechanism were also studied. The obtained results show that the introduction of PSSMA onto MGO can dramatically enhance the adsorption of Pb(II) and Cu(II) onto MGO@PSSMA, the adsorption capacities are changed from 24.9 mg/g to 141.1 mg/g for Pb(II) and from 22.8 mg/g to 104.8 mg/g for Cu(II), respectively. Moreover, the adsorption of Pb(II) and Cu(II) onto MGO@PSSMA and MGO fits pseudo-second-order kinetic and Langmuir model well, respectively. In addition, the used MGO@PSSMA can be effectively regenerated with ethylenediaminetetraacetic acid (EDTA) and hydrochloric acid (HCI), and recovered from Pb(II) and Cu(II) aqueous solution under an external magnetic field.