Supported iron oxide nanoparticles (NPs) on natural fiber surfaces have enormous potential to develop wastewater depuration strategies. We describe here the fabrication and performance of a bionanocomposite based on cellulosic fique fibers (FF) decorated with magnetite (Fe3O4) NPs. The bionanocomposite material (FF/Fe3O4) functions as a heterogeneous Fenton-like catalyst for color removal from indigo carmine (IC)-containing solutions. Cellulose in FF undergoes an alkaline treatment, resulting in a heterogeneous and positively charged microstructure with channels and cavities acting as nanoreactors, facilitating size control, dispersion, and stabilization of the Fe3O4 NPs via an ultrasonic-assisted co-precipitation method. The FF/Fe3O4 bionanocomposite assembly was monitored using FESEM, XPS, ATR-IR, XRD, and TGA. The FF/Fe3O4 bionanocomposite removed up to 90% of the color in IC-spiked model aqueous samples through Fenton-like reactions within 5 minutes for up to 10 cycles, as shown by UV-vis measurements and MS data. After treating a real effluent from a denim factory with the FF/Fe3O4 composite for 120 minutes, we observed reductions of 24% in chemical oxygen demand (COD), 100% in surfactant content, 99% in true and apparent color, and 99% in turbidity.