Regulations on methane emissions from lean-burn natural gas (NG) and lean-burn dual fuel (natural gas and diesel) engines are becoming more stringent due to methane’s strong greenhouse effect. Palladium-based oxidation catalysts are typically used for methane reduction due to their relative high reactivity under lean conditions. However, the catalytic activity of these catalysts is inhibited by the water vapor in exhaust and decreases over time from exposure to trace amounts of sulfur. The reduction of deactivated catalysts in a net rich environment is known to be able to regenerate the catalyst. In this work, a multicycle methane light-off & extinction test protocol was first developed to probe the catalyst reactivity and stability under simulated exhaust conditions. Then, the effect of two different regeneration gas compositions, denoted as regen-A and regen-B, was evaluated on a degreened catalyst and a catalyst previously tested on a natural gas engine. The results from light-off & extinction test cycles reveal that the reactivity and stability of the Pd-based catalysts change upon reaction and the change becomes more significant upon regeneration. In general, the reactivity improvement from regeneration is temporary. Light-off temperatures are reduced right after regeneration, then the catalyst displays a reactivity decreasing trend. For the degreened catalyst, regen-A and regen-B have a similar effect at 500 °C. On the other hand, regen-A is ineffective at regenerating the engine tested catalyst, while the light-off performance of this catalyst was improved right after regen-B. Temperature-programmed-desorption (TPD) and temperature-programmed-reduction (TPR) were utilized to characterize sulfur removal during regeneration. Improved catalyst reactivity and stability was observed with increasing regen-B temperature and it was attributed to sulfur removal from the catalyst.