Micro- and nanofragments resulting from the decomposition of disposable plastic items might be dangerous for the environment and humans. A new approach based on a “green” environmental technology of microplastic particles removal by magnetic sedimentation is suggested. In order to remove polyethylene (PE, 10–200 µm) and polyethylene terephthalate (PET, 5–30 µm) particles from model aqueous suspensions (starting concentration of 0.1 mg/l), the composite magnetic Fe–C–NH2 particles (4–8 nm) were added, afterward, the magnetic sedimentation of the formed heteroaggregates in a gradient magnetic field produced by permanent magnets was conducted. Magnetic nanoseeds were synthesized by the gas condensation method and characterized by magnetization measurements. The conditions for the heteroaggregation and for the magnetic sedimentation of the heteroaggregates have been investigated. For this, the dynamic light scattering analysis, SEM, optical microscopy, XRD and UV-visible spectrophotometry were used. The amount of the added magnetic nanoparticles (0.005 g/l) is less for the PET compared to the PE microparticles, which can be caused by a combination of several factors, in particular, by a higher hydrophilicity of PET particles which promotes a more active attachment of magnetic nanoparticles. For a more efficient removal of both plastic and magnetic particles from water, an increased up to 3–5 h time exposure for the heteroaggregation is recommended. At the magnetic field gradients up to dB/dz = 90 T/m, a 100-fold reduction in the plastics concentration in water after 15 min was achieved.