The addition of Ni2+, Zn2+, Fe2+ and Co2+ to the carbonaceous materials obtained from waste exhausted solid sludges and their use in the heterogeneous anaerobic reduction of aqueous solutions of the azo dye acid orange II (AOII) in a continuous up flow packed bed biological reactor (UPBR) were investigated. The surface chemistry of new sludge based catalysts (SBCs) was characterized by various tools in order to reveal the physico-chemical properties of the materials. The catalysts were also tested for isotherm batch adsorption with AOII dye showing good fitting to the Langmuir isotherm. The impregnation process of the dried sludge was carried out through 1 mol/L solution of salts of the different metals, followed by carbonization at 600 °C. In the UPBR, high values of AOII dye reduction were achieved at very short space times (τ). AOII conversion was 78% for SBCZn600, 57% for SBCFe600, and 55% for SBCNi600 at a space time of 1.0 min, comparable with that obtained with commercial activated carbons (CAC). 97% of AOII conversion was achieved for SBCFe600 catalyst at 4.0 min of space time, during 100-days continuous operation without loss of catalytic activity. The results show that the catalytic abilities of impregnated catalyst in the heterogeneous anaerobic reduction of dye molecules is depended on the distribution of metal particle on the surface and, can substitute commercial activated carbons for their use in the elimination of contaminated dye solutions from textile industries.