Increased use of natural gas as a fuel in efficient, lean-burning engines could offer environmental advantages, but this necessitates a catalytic oxidation of methane escaping from the engine. The challenge for the catalytic oxidation of CH4 is that the catalyst must operate in the exhaust, which contains H2O (5–15 vol %) and SO2 (∼1 ppm), and both components cause a severe inhibition of the catalyst. Here, we report that a 2 wt % Rh/ZSM-5 catalyst offers great promise by showing that high methane conversion can be reached at practically achievable conditions and high space velocities also in the presence of H2O and SO2. Rh-based catalysts, which are in the form of Rh2O3 under reaction conditions, become superior to the state-of-the-art Pd-based catalysts in an atmosphere with both H2O and SO2. Although both H2O and SO2 inhibit Pd and Rh catalysts, water is found to have a destabilizing effect on rhodium sulfate that enables a partial decomposition of the sulfate below 400 °C. We propose that this partly alleviates the sulfur poisoning of Rh catalysts; wherefore, the combined inhibition from H2O + SO2 is weaker for Rh than that for Pd.