Lean-burn natural gas (NG) engines are used world-wide for both stationary power generation and mobile applications ranging from passenger cars to Class 8 line-haul trucks. With the recent introduction of hydraulic fracturing gas extraction technology and increasing availability of natural gas, these engines are receiving more attention. However, the reduction of unburned hydrocarbon emissions from lean-burn NG and dual-fuel (diesel and natural gas) engines is particularly challenging due to the stability of the predominant short-chain alkane species released (e.g., methane, ethane, and propane). Supported Pd-based oxidation catalysts are generally considered the most active materials for the complete oxidation of low molecular weight alkanes at temperatures typical of lean-burn NG exhaust. However, these catalysts rapidly degrade under realistic exhaust conditions with high water vapor concentrations and traces of sulfur. The impact of sulfur poisoning and the regeneration of the degraded Pd-based oxidation catalyst by thermal and reductive regeneration were investigated. Thermal regenerations beginning at 500°C recover some catalyst performance when performed in the absence of sulfur. However, in an exhaust environment, where sulfur is always present at trace levels, thermal regeneration may prove impractical. Reductive regenerations successfully remove sulfur and recover catalyst activity, with sulfur removal occurring rapidly in the complete absence of O2.