Red mud waste from the aluminium industry was modified by leaching using hydrochloric acid or oxalic acid with additives, followed by precipitation or evaporation. The prepared catalysts were characterized in detail and tested for toluene total oxidation. The samples prepared by precipitation of the leachate by adding a base gave a much better performance in catalytic oxidation than the ones prepared by just evaporating the leachate. These improved performances can be correlated to the enhanced textural and redox properties of the catalysts due to the better dispersion and higher enrichment of Fe oxides at their surface. The best performing catalyst had a light-off temperature of around 310 °C and complete oxidation took place at around 380 °C.