Ultra-fast toxic metals removal using a hybrid and nanostructured vaterite- poly(ethyleneimine) (NV-PEI) is reported. Especially for Pb2+ an extremely high and fast adsorption capacity without precedents is observed. Within a 3 min contact time (CT) 97-100% of Pb2+ contaminant in water samples at pH 6 with a large concentrations range (from 2 to 1000 ppm) and using a dosage of 0.5 g NV-PEI/L have been removed. The maximum adsorption capacity (qmax) calculated for a 1500 ppm Pb2+ initial concentration was 2762 mg of Pb2+/g NV-PEI. In addition to the excellent Pb2+ removal, this material is cheap, easy to be synthesized, biocompatible, biodegradable, which makes it superior to others reported so far and an attractive alternative for treatment of industrial wastewaters.