Perovskite derived Ni catalysts offer the remarkable benefit of regeneration after catalyst poisoning or Ni particle growth through the reversible segregation of Ni from the perovskite-type oxide host. Although this property allows for repeated catalyst regeneration, improving Ni catalyst stability towards sulfur poisoning by H2S is highly critical in solid oxide fuel cells. In this work Mn, Mo, Cr and Fe were combined with Ni at the B-site of La0.3Sr0.55TiO3 +/- to explore possible benefits of segregation of two transition metals towards sulfur tolerance. Catalytic activity tests towards the water gas shift reaction were carried out to evaluate the effect of the additional metal on the catalytic activity and sulfur stability of the Ni catalyst. The addition of Fe to the Ni perovskite catalyst was found to increase sulfur tolerance. The simultaneous segregation of Fe and Ni from La0.3Sr0.55Ti0.95-xNi0.05FexO3 +/- (x 0.05) was investigated by temperature programmed reduction, X-ray diffraction and X-ray absorption spectroscopy and catalytic tests after multiple redox cycles. It is shown that catalytic properties of the active phase were affected likely by the segregation of Ni/Fe alloy particles and that the reversible segregation of Ni persisted, while it was limited in the case of Fe under the same conditions.