This work reports for the first time on a new finding of luminescent CePO4:Tb nanocrystals providing a novel oxygen sensing material on the basis of the redox responsive reversible luminescence in an oxidizing/reducing atmosphere. The origin of the luminescence quenching/recovery of nanocrystalline CePO4:Tb was clearly demonstrated, from the surface chemistry of nanocrystals and the fluorescence decay dynamics of Tb(III). Our present work represents a preliminary demonstration of the feasibility of using nanocrystalline CePO4:Tb as a novel oxygen sensing material since it yields several advantages including surfactant-free synthesis, dual detection functioning, rapid response, high sensitivity and good reproducibility.