Per- and polyfluoroalkyl substances (PFAS) are ubiquitous in many consumer products and present serious environmental challenges due to their persistent nature. Currently, conventional water treatment methods fail to remove PFAS, and other newly proposed materials/techniques face challenges when employed under realistic conditions. This study reports on poly(ethylenimine)-functionalized cellulose microcrystals (PEI-f-CMC) that showed a near-instant and high removal of PFAS under concentrations relevant to their actual occurrence in the natural environment (i.e., <1000 ng/L). The selective removal efficiency of 22 PFAS from different classes (i.e., legacy carboxylic and sulfonated PFAS, emerging carboxylic and sulfonated PFAS, and PFAS-precursors) using PEI-f-CMC was confirmed in lake water as well as solutions codosed with two additional types of natural organic matter. The performance of PEI-f-CMC was maintained in eight consecutive adsorption/regeneration cycles to remove PFAS. The PEI-f-CMC with its unique fast kinetics and high adsorption activity toward PFAS exhibits a great potential for being a promising alternative adsorbent for PFAS control.