Activated clay minerals have been widely used in the edible oil refining industry for decolorization of crude oil by adsorption, and so far many methods have been used to improve their decolorization efficiency. Herein, we successfully prepared a series of carbon/attapulgite (C/APT) composite adsorbents by a one-step in-situ carbonization process with natural starch (St) as the carbon source. It has been revealed that the adsorbent had better decolorization efficiency for crude palm oil than acid-activated APT. However, more than a million tons of decolorized waste is produced every year in the oil-refining industry, which was often treated as solid waste and has not yet been reutilized effectively. In order to explore a viable method to recycle and reuse the decolorant, the waste decolorant was further prepared into new C/APT adsorbents for the removal of dyes from wastewater, and then the dyes adsorbed on the adsorbent were used as the carbon sources to produce new C/APT adsorbents by a cyclic carbonization process. The results showed that the adsorbents prepared from the decolorized waste could remove more than 99.5% of the methylene blue (MB), methyl violet (MV), and malachite green (MG) dyes from the simulated wastewater with the dye concentration of 200 mg/L, and the C/APT–Re adsorbent consecutively regenerated five times using the adsorbed dyes as a carbon source still exhibit good adsorption efficiency for dyes. As a whole, this process opens a new avenue to develop efficient decolorants of palm oil and achieves recyclable utilization of decolored waste.