The catalytic combustion of <1% methane in air over palladium-based catalysts is investigated. The influence of operating parameters and pretreatment conditions on the activity and stability of the catalysts is studied. X-ray photoelectron spectroscopy analysis of Pd/Al2O3 indicates the emergence of Pd carbide, even under lean conditions (0.6% methane) and at temperatures as low as 180°C. Significant differences were observed in the light-off temperatures and extent of coke deposition, depending on whether the catalysts were conditioned under oxidizing or reducing conditions. The oxidized palladium catalysts were reduced by methane under reaction conditions and exhibited similar activity compared to catalysts which were activated under hydrogen. Time-on-stream experiments reveal that the stability of the Pd/Al2O3 catalyst reduced in hydrogen was only marginally improved compared to catalysts calcined in air.