A novel Pd supported on TS-1 combustion catalyst was synthesized and tested in methane combustion under very lean and under highly humid conditions (<1%). A notable increase in hydrothermal stability was observed over 1900 h time-on-stream experiments, where an almost constant, steady state activity obtaining 90% methane conversion was achieved below 500 °C. Surface oxygen mobility and coverage plays a major role in the activity and stability of the lean methane combustion in the presence of large excess of water vapour. We identified water adsorption and in turn the hydrophobicity of the catalyst support as the major factor influencing the long term stability of combustion catalysts. While Pd/Al2O3 catalyst shows a higher turn-over frequency than that of Pd/TS-1 catalyst, the situation reversed after ca. 1900 h on stream. Two linear regions, with different activation energies in the Arrhenius plot for the equilibrium Pd/TS-1 catalyst, were observed. The conclusions were supported by catalyst characterization using H2-chemisorption, TPD, XPS analyses as well as N2-adsorption-desorption, XRD, SEM, TEM. The hydrophobicity and competitive adsorption of water with oxygen is suggested to influence oxygen surface coverage and in turn the apparent activation energy for the oxidation reaction.