Abstract The synergistic combination of different nanomaterials for improved performance in environmental applications such as the removal of aqueous micropollutants has attracted increasing interest in recent years. This study demonstrates a novel sequential adsorption–aggregation concept that harnesses tubular halloysite nanotubes (HNTs) and flexible cellulose nanofibrils (CNFs) for the removal of a small, anionic dye molecule, chrome azurol S, from water. Hollow HNTs were first allowed to interact with the aqueous dye solution, after which the dye-loaded colloidal nanotubes were aggregated and separated from the water phase with cationized CNFs. The combination of 25 mg CNFs with 1 g HNTs at pH 7 resulted in efficient removal of dye (80%) and turbidity (~100%) and the removal of dye was further promoted in more acidic conditions (within the pH range of 6–8.5) because of the attractive electrostatic interactions. Cationic CNFs not only enabled the separation of dye-loaded clay particles from the water phase through a rapid aggregation but also participated in dye removal through adsorption (~20%). In comparison with nano-sized HNTs, the dye removal performance of micro-sized and chemically similar kaolin was poor (43%). Given the good availability of both HNTs and CNFs and the low consumption of the more expensive component (i.e., CNFs) in the process, the concept is straightforward, readily applicable, environmentally benign, and potentially cost-effective.