Abstract: Catalytic combustion of methane was studied over Ce0.5Zr0.5O2 and CeO2 supported Pd (Pd/CZ and Pd/Ce) catalysts in the presence of SO2. The effect of sulfation (air including 100 ppm SO2 for 6 h at 500 °C) on the sulfur-tolerant performance of the catalysts was also investigated. Results indicated that there is a considerable promotion effect for CH4 complete oxidation on Pd/CZ catalyst, while the activity of Pd/Ce catalyst was inevitably inhibited. Further, the superior sulfur-tolerant behavior of Pd/CZ was verified through a 50 h time-on-stream stability test. Mechanistic insights into the synergistic effect between the support and Pd were unveiled by Raman, H2-TPR, XPS, NH3-TPD, DRIFTS, HAADF-STEM, etc. It was deduced that the formation of sulfates at the Pd-support interface could promote the dissociative adsorption of methane on Pd/CZ catalyst. Meanwhile, the higher relative acid strength and the acid amount were also decisive factors for the high sulfur-resistant performance. The enhanced acid strength and acid amount prevented the further formation of bulk-like sulfate species for the SO2 treated Pd/CZ catalyst, thus enhancing the sulfur-tolerant ability of the catalyst.