In this work, the use of a residue-based catalyst for heterogeneous photo-Fenton of Reactive black 5 (RB5) textile dye was evaluated. The catalyst was prepared by chemical vapor deposition of ethanol on a red mud residue, an important waste of the aluminum industry rich in iron oxide. The catalyst was characterized by different techniques, i.e., Mössbauer spectroscopy, Raman spectroscopy, CHN elemental analysis, BET surface area, and scanning and transmission electron microscopies. Results showed that the iron phases present in the red mud are reduced and a carbon coating is formed, protecting the catalyst from excessive iron leaching. The photo-Fenton experiments were carried out by varying pH, H2O2 concentration and radiation power and assessing dye conversion as the response variable. Studies on textile dye degradation showed that low pH favors the reaction and 100% photo-degradation efficiency was obtained, reducing the toxicity of the dye. The best operational condition was achieved at pH 3 and H2O2 initial concentration of 11 mM, after 60 min of reaction. Kinetic data related to RB5 dye degradation were well fitted to the Langmuir–Hinshelwood model in the range of 20–50 mg L−1 of RB5 initial concentration with obtained initial rate constant of 9.4 × 10−8 mol L−1 min−1. A reaction pathway was proposed in which the H2O2 is activated by surface Fe2+ sites on RM based catalyst, especially in the presence of light, producing OH radicals in a heterogeneous photo-Fenton-like mechanism to oxidize the organic pollutant Reactive black 5 dye.