Catalytic combustion of CH4 to CO2 and H2O was studied over zeolite-supported Pd catalysts, and it was found that zeolite-supported Pd catalysts can present pronounced discrepancy in the catalytic performance of methane oxidation when Na-ZSM-5 was ion-exchanged with various cations of La, Ni, and Mg. Very interestingly, the Pd catalyst supported by NaLa-ZSM-5 exhibited the best result. Over an optimized catalyst, a complete conversion of methane can be achieved at around 320 °C, which is about 60 °C lower than the temperature needed for Pd/Na-ZSM-5. Physicochemical characterizations such as XRD, SEM, HRTEM, XPS, and ICP-OES techniques were used to investigate the factors influencing the catalytic activity and find out the reasons behind the discrepancy in the catalytic performance of methane combustion over these zeolite-supported Pd catalysts. Based on the characterization results, it is proposed that the Pd dispersion and its chemical states are major factors that govern catalytic performance of methane combustion over these catalysts. To the best of our knowledge, the optimal catalyst in this study stands out compared with other reported similar Pd catalysts for the catalytic combustion of methane in terms of activity.