The perovskite-type mixed oxide La0.3Sr0.55Ti0.95Ni0.05O3−δ (LSTN) is demonstrated to exhibit the remarkable property of structural regeneration, where Ni can be reversibly exsoluted from the host perovskite lattice resulting in a regenerable Ni catalyst for solid oxide fuel cell anode applications. Results of catalytic tests for the water gas shift reaction and electrochemical investigations on a button-sized fuel cell demonstrate the redox stability of LSTN, its potential application in solid oxide fuel cells, and its ability to recover catalytic activity completely after sulfur poisoning. Nickel segregation was characterized and quantified on powder samples by means of electron microscopy, X-ray diffraction, X-ray absorption spectroscopy, and temperature-programmed reduction–reoxidation cycles. Catalyst stability was much improved compared to impregnated Ni/La0.3Sr0.55TiO3−δ and Ni/Y0.08Zr0.92O2 anode materials. A full cell was tested under both open circuit voltage and polarized conditions, showing a stable cell voltage over redox cycles as well as periods of reverse potential and current overload. The area-specific resistance of the anode layer was as low as 0.58 Ω cm2 at 850 °C. This allows LSTN to be applied in redox-stable solid oxide fuel cell anodes and reversible segregation of Ni to be exploited for fast recovery from sulfur poisoning.