Increasing the use of natural gas engines is an important step to reduce the carbon footprint of mobility and power generation sectors. To avoid emissions of unburnt methane and the associated severe greenhouse effect of lean-burn engines, the stability of methane oxidation catalysts against steam-induced sintering at low temperatures (<500 °C) needs to be improved. Here we demonstrate how the combination of catalyst development and improved process control yields a highly efficient solution for complete methane oxidation. We design a material based on palladium and hierarchical zeolite with fully sodium-exchanged acid sites, which improves the support stability and prevents steam-induced palladium sintering under reaction conditions by confining the metal within the zeolite. Repeated short reducing pulses enable the use of a highly active transient state of the catalyst, which in combination with its high stability provides excellent performance without deactivation for over 90 h in the presence of steam.