We studied structure and oxygen-sensitive photoluminescence (PL) of ZrO2:Eu,Nb nanocrystalline powders synthesized via a sol-gel route and heat-treated up to 1200 °C. The material containing only 2 at% Eu3+ was predominantly monoclinic, whereas 8 at% of Eu3+ stabilized tetragonal phase. Comparable amount of niobium co-doping effectively suppressed the formation of tetragonal phase. PL of Eu3+ ions was observed under direct excitation at 395 nm. PL decay kinetics showed that the luminescence was partially quenched, depending on doping concentrations and ambient atmosphere. At 300 °C, the PL intensity of all samples systematically responded (with up to 70% change) to changing oxygen content in the O2/N2 mixture at atmospheric pressure. At low doping levels, the dominant factor controlling the PL intensity was an energy transfer from excited PL centers to randomly distributed defects in the ZrO2 lattice. We argue that the charge transfer between the defects and adsorbed oxygen molecules alters the ability of the defects to quench Eu3+ luminescence. At high doping levels, another type of sensor response was observed, where some Eu3+ emitters are effectively switched on or off by the change of ambient gas. A remarkable feature of the studied material is a reversing of the sensor response with the variation of the Nb concentration.