In this study, a new cellulose nanofibril (CNF) composite aerogel was fabricated using a green and facile mussel-inspired coating strategy. First, the CNF hydrogel was crosslinked by calcium ion followed by immersion in dopamine solution. Second, the surface of CNF was modified using polydopamine (PDA) to obtain PDA@CNF (PCNF) composite aerogel. The PCNF composite aerogels had large surface areas (368.15 m2/g) and low bulk density (27.2 mg/cm3). The composite aerogel exhibited improved mechanical properties, which were almost three times compared with those of CNF aerogel. Moreover, PCNF composite aerogel had good resilience under a wet state. The PDA functional layer remarkably enhanced the adsorption capacities of the composite aerogel for methylene blue (MB). The maximum adsorption of MB was 208 mg/g at an initial dye concentration of 50 mg/L. The adsorption isotherm and kinetic behaviors of the composite aerogel were consistent with Langmuir and pseudo-second-order models. In addition, the PCNF composite aerogels had a high adsorption capacity over a wide pH range. The reuse experiment showed that the removal efficiency of the composite aerogel remained higher than 85% after five cycles. Therefore, PCNF composite aerogels may have potential application in wastewater treatment due to its environmental sustainability and low energy consumption.