This work involves in situ FT-IR spectroscopic study of the routes of formation, composition and thermal stability of strongly bound NOx complexes on the surface of Pd/tungstated zirconia, and transformation of the surface NOx complexes in the presence of methane in order to elucidate the mechanism of selective catalytic reduction of NO with methane. Sol-gel polymer-template synthesis was chosen to obtain high surface area in the preparation of the tungstated zirconia used as support (WO3 nominal content of 18.6 wt %). The Pd(II) ions (0.1 wt%) have been deposited by impregnation. PXRD characterization shows that the support and the catalyst are tetragonal and contain mesoporous phase. The adsorption of NO at room temperature on the tungstated zirconia shows presence of coordinatively unsaturated Zr(IV) ions. The spectrum of NO adsorbed on palladium modified on tungstated zirconia reveals the existence of two types of Pd(II) sites. No exposed Zr(IV) ions are observed. The surface NOx species (N2O3, nitro and nitrito ions) on both samples are produced at room temperature by oxidation of NO with the W6+=O species. In the case of the Pd/tungstated zirconia, palladium(II) can oxidize NO to NO2 at 623 K. The adsorption of NO/O2 mixture at room temperature on the samples studied leads to formation of various kinds of surface nitrates characterized by different modes of coordination. The thermal stability of the nitrate species formed on both samples is comparable: They disappear after dynamic evacuation at 673 K. However, lower concentration of the surface nitrates on the Pd/tungstated zirconia compared to that on the tungstated zirconia indicates that in the former case the nitrates are coordinated to the support. The experimental results show that methane interacts differently with the NOx-precovered tungstated zirconia and Pd/tungstated zirconia although both materials are able to activate methane at the same temperature in absence of adsorbed NOx species. In the case of the tungstated zirconia the surface nitrates suppress the oxidation of methane, whereas the NOx-precovered Pd/tungstated zirconia catalyzes the formation of nitromethane. The latter compound is considered as a key intermediate in the selective catalytic reduction of NO with methane in excess oxygen. A mechanism, which involves direct activation of methane by the catalyst, leading to the products of the selective reduction (N2, CO2 and H2O) is proposed.