This work investigates the regeneration of S-poisoned Pd/Al2O3 and Pd/CeO2/Al2O3 catalysts under different CH4 containing atmospheres. Under lean combustion conditions in the presence of excess O-2, partial regeneration took place for both systems only above 750 degrees C after decomposition of stable sulphate species adsorbed on the support. Under alternate lean combustion/CH4-reducing pulse regeneration is markedly anticipated down to 550-600 degrees C. Experiments evidenced an effective role of certain preventing PdO from sulphation and in promoting regeneration via sulphates decomposition under reducing conditions.