More efficient lean-burn, natural gas engines are limited by greenhouse gas emissions due to methane oxidation catalysts (MOC) that suffer from water inhibition and high temperature activation. Herein, we report that the addition of Mg to supported 1 wt.% Pd MOCs improved hydrothermal stability even after severe hydrothermal aging. The superior methane oxidation activity compared to the corresponding Mg-free catalyst was attributed to (1) influence of Mg during surface roughening and restructuring at 700 °C on metal-support interaction, (2) reducibility of PdOx sites and (3) preferential stabilization of active Pd (1 0 0) facets in the sample as was evidenced by H2 TPR and CO TPD characterization experiments. Methane conversion under synthetic exhaust conditions relevant to natural gas, lean-burn engines were investigated. BET, TPR, CO pulse chemisorption followed by TPD provided valuable insights into the surface area, pore volume, reducibility, Pd dispersion and Pd particle size of the selected catalyst samples.