The catalytic NO reduction by methane was studied using a (NO,CH4,Ar),Pt|polybenzimidazole(PBI)–H3PO4|Pt,(H2,Ar) fuel cell at 135 and 165°C. It has been found that, without any reducing agent (like CH4), NO can be electrochemically reduced in the (NO, Ar), Pt/C|PBI–H3PO4|Pt/C, (H2,Ar) fuel cell with participation of H+ or electrochemically produced hydrogen. When added, methane partially suppresses the electrochemical reduction of NO. Methane outlet concentration monitoring has shown the CH4 participation in the chemical catalytic reduction, i.e., methane co-adsorption with NO inhibited the electrochemical NO reduction and introduced a dominant chemical path of the NO reduction. The products of the NO reduction with methane were N2, C2H4, and water. The catalytic NO reduction by methane was promoted when the catalyst was negatively polarized (−0.2 V). Repeated negative polarization of the catalyst increased the NO conversion. Maximum NO conversion was 48%. This effect was explained as a result of the reaction of the electrochemically produced hydrogen.