We show that the first stages of interaction between NO and reduced ceria comprise the formation of azides, N3(-), with simultaneous oxidation of Ce(3+) to Ce(4+). This finding imposes revision on some current views of catalytic NO conversion and may contribute to design of new deNOx materials and processes.