The deactivation of supported nickel catalysts by coking is an important technological subject for many chemical processes, especially when high concentrations of unsaturated hydrocarbons are present in the feed gas. Here, the reversible segregation of Ni from a LaFeO3 +/-delta perovskite-type host lattice was exploited to completely recover a LaFe0.8Ni0.2O3 +/-delta catalyst after it had been deliberately subjected to severe carbon deposition during CO2 methanation in ethylene rich feed gas for several hours. Temperature programmed reduction, X-ray diffraction, electron microscopy, X-ray absorption spectroscopy and catalytic activity tests were used to follow the catalyst structure along the various steps of reduction, reaction, coking and subsequent regeneration, while Raman spectroscopy and electron microscopy were used to characterize the nature of the carbon deposits. It is shown that upon reduction Ni atoms segregate to the surface of the perovskite to form catalytic active Ni particles. Oxidation stimulates Ni atoms to readopt the coordination environment of Fe in the perovskite matrix. This property persisted after severe catalyst deactivation by filamentous, partially graphitic carbon. It is demonstrated that simple catalyst reoxidation can be applied to oxidize all carbon deposits while additionally reverting segregated Ni back into the host lattice, thus protecting Ni from particle growth and resultant long-term loss of catalyst activity over multiple regeneration cycles.