A new cathodic material for electro-Fenton (EF) process was prepared based on a macroscopic fiber (CNTF) made of mm-long carbon nanotubes directly spun from the gas phase by floating catalyst CVD, on a carbon fiber (CF) substrate. CNTF@CF electrode is a highly graphitic material combining a high surface area (~260 m2/g) with high electrical conductivity and electrochemical stability. One kind of azo dye, acid orange 7 (AO7), was used as model bio-refractory pollutant to be treated at CNTF@CF cathode in acidic aqueous medium (pH 3.0). The experimental results pointed out that AO7 and its organic intermediate compounds were totally mineralized by hydroxyl radical generated from Fenton reaction. In fact, 96.7% of the initial total organic carbon (TOC) was eliminated in 8 h of electrolysis by applying a current of −25 mA and ferrous ions as catalyst at concentration of 0.2 mM. At the same electrolysis time, only 23.7% of TOC removal found on CF support which proved the high mineralization efficiency of new material thanks to CNTF deposition. The CNTF@CF cathode maintained stable its activity during five experimental cycles of EF setup. The results indicated that CNTF@CF material could be a potential choice for wastewater treatment containing bio-refractory by electrochemical advanced oxidation processes.