Water, which is an intrinsic part of the exhaust gas of combustion engines, strongly inhibits the methane oxidation reaction over palladium oxide-based catalysts under lean conditions and leads to severe catalyst deactivation. In this combined experimental and modeling work, we approach this challenge with kinetic measurements in flow reactors and a microkinetic model, respectively. We propose a mechanism that takes the instantaneous impact of water on the noble metal particles into account. The dual site microkinetic model is based on the mean-field approximation and consists of 39 reversible surface reactions among 23 surface species, 15 related to Pd-sites, and eight associated with the oxide. A variable number of available catalytically active sites is used to describe light-off activity tests as well as spatially resolved concentration profiles. The total oxidation of methane is studied at atmospheric pressure, with space velocities of 160,000 h−1 in the temperature range of 500–800 K for mixtures of methane in the presence of excess oxygen and up to 15% water, which are typical conditions occurring in the exhaust of lean-operated natural gas engines. The new approach presented is also of interest for modeling catalytic reactors showing a dynamic behavior of the catalytically active particles in general.