This letter reports a catalyst which has practical activity and durability for the reduction of nitrogen oxides by methane in the presence of water vapor and sulfur oxides. The catalyst is sulfated zirconia loaded with palladium and platinum. The catalyst maintained an NOx conversion higher than 50% for over 100 h in the presence of 9% water vapor and 3 ppm SO2, where Pd-loaded mordenite lost almost all activity in 50 h.