The role of methanol in the NOx reduction into N2 has been investigated with the multifunctional catalyst H3PW12O40·6H2O−Pt (HPW−Pt) supported on CexZr4-xO8. The reduction of NOx is obtained by a two-stage operation: in the first period, during the lean mode (2 min), NOx (NO/NO2 = 1) are stored in the catalyst; then they are reduced in N2 during the rich period (methanol injection 1 min). With methanol, the NOx storage efficiency of HPW−Pt/CexZr4-xO8 is stable and very high (ca. 100%). It is directly related to the exchange of HPW structural water with methanol. Around 55% of stored NOx are transformed into N2 by alternative lean/rich cycles. CxHyOz intermediate species derived from methanol are proposed as intermediate reductants for NOx.