A proton exchange membrane fuel cell (PEMFC) gas sensor is a promising and novel gas sensing device. However, the poor sensitivity and strong cross sensitivity of commercial carbon-supported-platinum (Pt/C) remain obstacles to its utilization. Here, we demonstrate that the issue can be addressed using mesoporous titanium niobium nitrides (Ti0.75Nb0.25N) synthesized using a solid-solid phase separation process. Pt nanoparticles supported on ternary transition metal nitrides enable the strong metal support interaction (SMSI), which changes the surface electronic structure and catalytic activity of the electrode material. Compared with the Pt/C-sensor, the selectivity of the Pt/Ti0.75Nb0.25N-based sensor to formaldehyde (HCHO) is significantly higher, while the response to other gases is effectively inhibited. In mixed gas tests, HCHO sensing of the Pt/Ti0.75Nb0.25N-sensor is still not affected (within 3.5% of the standard deviation limit). Furthermore, the Pt/Ti0.75Nb0.25N-sensor exhibits a much higher sensitivity (0.208 μA per ppm) toward HCHO when compared to the Pt/C-sensor (0.058 μA per ppm). The Pt/Ti0.75Nb0.25N-sensor also exhibits extraordinary long-term stability due to its electrochemical stability and SMSI of the electrode material. This work hence points to the design and development of a new sensing electrode system, which offers a combination of high selectivity and sensitivity when used in fuel-cell gas sensors.