The recycling and recovery of value-added secondary raw materials such as spent Zn/C batteries is crucial to reduce the environmental impact of wastes and to achieve cost-effective and sustainable processing technologies. The aim of this work is to fabricate reduced graphene oxide (rGO)-based sorbents with a desulfurization capability using recycled graphite from spent Zn/C batteries as raw material. Recycled graphite was obtained from a black mass recovered from the dismantling of spent batteries by a hydrometallurgical process. Graphene oxide (GO) obtained by the Tour’s method was comparable to that obtained from pure graphite. rGO-based sorbents were prepared by doping obtained GO with NiO and ZnO precursors by a hydrothermal route with a final annealing step. Recycled graphite along with the obtained GO, intermediate (rGO-NiO-ZnO) and final composites (rGO-NiO-ZnO-400) were characterized by Wavelength Dispersive X-ray Fluorescence (WDXRF) and X-ray diffraction (XRD) that corroborated the removal of metal impurities from the starting material as well as the presence of NiO- and ZnO-doped reduced graphene oxide. The performance of the prepared composites was evaluated by sulfidation tests under different conditions. The results revealed that the proposed rGO-NiO-ZnO composite present a desulfurization capability similar to that of commercial sorbents which constitutes a competitive alternative to syngas cleaning.