Catalytic methane oxidation is used in exhaust gas aftertreatment to reduce methane emissions from lean burn natural gas vehicles as well as in stationary combustion processes. Pd/zeolite catalysts provide high activity for this reaction, but they deactivate rapidly under the reaction conditions and in the presence of steam due to extensive palladium nanoparticle sintering, which is a common deactivation pathway for supported catalysts. Understanding the origin of this phenomenon is crucial for improving the performance of such materials. In this work, we identify all stability and activity descriptors of Pd/zeolites fully exchanged with sodium. On the basis of these descriptors we design an active and stable catalyst using a synthetic approach which comprises the formation of mesopores in the zeolite by mild desilication, removal of surface and extraframework aluminum by selective dealumination, and complete sodium postexchange. This allows unstable Pd/H-ZSM-5 to turn into a highly active sintering-resistant hierarchical Pd/Na-ZSM-5 for the demanding reaction of complete methane oxidation. This synthetic procedure can be applied to other zeolites to enhance the stability of supported catalysts that are prone to sintering.