SO2 poisoning of methane oxidation over alumina-supported, Pd@CexZr1−xO2 nanoparticle catalysts was systematically studied by means of advanced PhotoElectron Spectroscopy (PES) methods. The Pd@CexZr1−xO2 units were synthesized and deposited on two modified-alumina supports, i.e. high surface area modified alumina and a model alumina prepared by Atomic Layer Deposition (ALD) of alumina on Indium Tin Oxide (ITO)/quartz slides. The model support was designed to be suitable for PES analysis and was stable to high temperature treatments (850°C). Characterization of the high-surface-area (HSA) catalysts by X-Ray Diffraction (XRD), N2 physisorption, CO chemisorption and Transmission Electron Microscopy (TEM) indicated formation of CeO2–ZrO2 (CZ) mixed-oxide crystallites that stabilize the Pd active phase against sintering. Correlation of methane-oxidation rates with PES results demonstrated two distinct mechanisms for deactivation by SO2. Below 450°C, the presence of SO2 in the feed led to partial reduction of the active PdO phase and to the formation of sulfates on the Pd. Above 500°C, poisoning by SO2 was less severe due to spillover of the sulfates onto the oxide promoter. Pd@ZrO2 catalysts showed the best resistance to SO2 poisoning, outperforming analogous Pd@CZ mixed-oxide catalysts, because there was less sulfate formation and the sulfates that did form could be removed during regeneration.