PdO is known to efficiently catalyze the oxidation of methane but suffers tremendously from sulfur poisoning that lowers its catalytic activity. In this paper, dispersion-corrected density functional theory based first principles calculations were performed to systematically screen the metal impurities M (where M is a transition metal) on a Pd1-xMxO catalyst that promote the desired adsorption energies for CH4 and SO2 to gain insights into the design of sulfation-resistant PdO-based methane oxidation catalysts. Specific Pd1-xMxO(101) catalyst was identified to thermodynamically avoid surface sulfation while maintaining the active sites for methane activation at typical experimental conditions. Results indicate a potential route of tuning the catalytic property of PdO by the introduction of a surface metal impurity. Graphic