An increasing body of evidence demonstrates that there is a direct correlation between global warming and the release of heavy metals into drinking and crop water supplies, and water security remains a pressing sustainability challenge in developing nations. We present a pathway to obtain ultra-stable nanofibers assembled from small molecules in water which rival the mechanical properties of nature's stiffest materials. We then decorate the surface of these nanofibers with efficient heavy metal chelators and demonstrate orders of magnitude improvement over macroscopic alternatives in use today, offering a way to miniaturize water treatment while overcoming several complications of existing strategies.