Rates and products of the (3 + alpha)NO + CH4 --> 1/2(3 + alpha)N-2 + (1 - alpha)CO + alpha CO2 + 2H(2)O (0 less than or equal to alpha less than or equal to 1) reaction were determined in low-pressure (NO/CH4/O-2) mixtures ([NO] <1 mu M,[CH4] < 10[NO], [O-2] less than or equal to [NO]; 1 mu M = 82 ppm at 1 atm, 1000 K) flowing over Sm2O3 between 1000 and 1200 K. Samaria pretreated with CH4 (or N-2) at reaction temperatures instantly releases N-2 when exposed to NO. Prompt CO formation also occurs on methane-conditioned samples. In contrast, stationary outflow gas compositions attain only after several reactor residence times following step (NO + CH4) injections to the untreated catalyst. Nitric oxide reduction rates R-No are roughly proportidnal to ([CH4] x [NO])(1/2) but do not extrapolate to zero at [NO] - 0 and always increase with T. We infer that : (1) there is no direct reaction between CH4 and NO on the catalyst surface; (2) instead, NO is reduced to N-2 by reaction with oxygen vacancies V, and with nonvolatile carbon-containing C-s species created in the heterogeneous oxidation/decomposition of CH4, respectively; (3) the entire mass, rather than just the surface, of catalyst microparticles participate in this phenomenon. We propose a purely heterogeneous mechanism in which physisorbed NO reacts with either vacancies in equilibrium with the active oxygen OR species responsible for CH4 oxidation or with C-s species. The derived kinetic law : R-(NO) = k(A)([NO](s)[CH4])(1/2) + (k(B)[CH4], with [NO](s) = [NO]/K-8(-1) + [NO]), in conjunction with the reported Arrhenius parameters, closely fits rates measured under anoxic conditions. The fact that R-NO is unaffected by O-2 UP to F-O2 similar to 0.3F(NO) but drops at larger F-O2 inflows, even if O-2 is fully consumed in CH4 oxidation, is consistent with the competition of NO and Oz for vacancies. The dissimilar observations made in experiments performed in the Torr range strongly suggest that solid catalysts promote combustion at such relatively high pressures.