Water contamination resulting from human activities leads to the deterioration of aquatic ecosystems. This restrains the access to fresh water, which is the leading cause of mortality worldwide. In this work, we developed a bio-based and water-resistant composite aerogel from renewable nanofibrils for water remediation application. The composite aerogel consists of two types of cross-linked nanofibrils. Poly(dopamine)-coated cellulose nanofibrils and amyloid protein nanofibrils are forming a double networked crosslinked via periodate oxidation. The resulting aerogel exhibits good mechanical strength and high pollutants adsorption capability. Removal of dyes (rhodamine blue, acriflavine, crystal violet, malachite green, acid fuchsin and methyl orange), organic traces (atrazine, bisphenol A, and ibuprofen) and heavy metal ions (Pb(II) and Cu(II)) from water was successfully demonstrated with the composite aerogel. More specifically, the bio-based aerogel demonstrated good adsorption efficiencies for crystal violet (93.1% in 30 min), bisphenol A (91.7% in 5 min) and Pb(II) ions (94.7% in 5 min), respectively. Furthermore, the adsorption–desorption performance of aerogel for Pb(II) ions demonstrates that the aerogel has a high reusability as maintains satisfactory removal performances. The results suggest that this type of robust and bio-based composite aerogel is a promising adsorbent to decontaminate water from a wide range of pollutants in a sustainable and efficient way.