Ectopically expressed olfactory receptors (ORs) have been linked with multiple clinically-relevant physiological processes. Previously used tissue-level expression estimation largely shadowed the potential role of ORs due to their overall low expression levels. Even after the introduction of the single-cell transcriptomics, a comprehensive delineation of expression dynamics of ORs in tumors remained unexplored. Our targeted investigation into single malignant cells revealed a complex landscape of combinatorial OR expression events. We observed differentiation-dependent decline in expressed OR counts per cell as well as their expression intensities in malignant cells. Further, we constructed expression signatures based on a large spectrum of ORs and tracked their enrichment in bulk expression profiles of tumor samples from The Cancer Genome Atlas (TCGA). TCGA tumor samples stratified based on OR-centric signatures exhibited divergent survival probabilities. In summary, our comprehensive analysis positions ORs at the cross-road of tumor cell differentiation status and cancer prognosis.