Fiber-based commodities represent a substantial fraction of plastic waste, leading to environmental harm. Discarded sanitary masks and fishing equipment undergo degradation, generating microfiber plastics, thereby presenting a notable hazard to both human health and the ecosystem. In this study, mechanically strong and environmentally friendly nanocomposite fibers were prepared by dry-jet wet spinning. The all-biomass-based fibers comprised agar and cellulose nanocrystals (CNC) as the matrix and nanofiller, respectively, and were highly miscible in deionized water as a cosolvent. Based on rheological characterization, the optimal spinning concentration and temperature were set to 13% (w/v) and 95 °C, respectively. The dry-jet wet-spun agar-based fibers exhibited remarkable mechanical performance compared with previously reported agar-based materials. In particular, the 1 wt% CNC (with respect to the agar amount) simultaneously improved the Young’s modulus, strength, and toughness by 8.3, 4.8, and 16.4% (2.6 GPa, 93.5 MPa, and 7.8 MJ m⁻³), respectively, compared to those of the control agar fibers (2.4 GPa, 89.2 MPa, and 6.7 MJ m⁻³), overcoming the trade-off of stiffness-toughness for conventional nanocomposite systems. In addition, the agar/CNC nanocomposite fibers rapidly adsorbed Methylene blue within 90 min, which is significantly faster than that of the film-type agar adsorbent. Therefore, all-biomass-based agar/CNC fibers are a promising remedy for alleviating water pollution.