Sulfur deactivation and regeneration behavior of the Pd/Al2O3 catalyst has been investigated via experimental characterization and density functional theory (DFT) simulations. During the sulfur exposure, PdO crystallites grow slightly while bulk Al2(SO4)3 forms on the support. DFT calculations indicate that SOx species interact strongly with the catalyst surface making it chemically inactive in agreement with the experimental results. During the regeneration treatment (CH4 conditions), PdO particles reduce, Al2(SO4)3 is partially removed, and the activity for CH4 conversion is increased. No full recovery can be observed due to remaining Al2(SO4)3, the formation of encapsulating sulfur species, and the partial reduction of PdO particles. To reoxidize Pd, the catalyst is further regenerated (O2 conditions). The resulting CH4 conversion is at the same level than with the regenerated catalyst. Thus, a small amount of Al2(SO4)3 appears to have a stronger effect on the performance than the state of Pd.