Accurate deconvolution of cell states from bulk tumor RNA-seq is hindered by heterogeneous malignant cells specifically in cancer applications. We present Statescope, a Bayesian framework that incorporates DNA-derived malignant cell purity to overcome this heterogeneity and explicitly models inter-sample variation to accurately identify cell states. Comprehensive benchmarking shows Statescope outperforms existing methods in both cell fraction and state estimation, and is unique in its ability to identify states entirely absent from single-cell references. In real-data applications, Statescope successfully recapitulates established cell states, including multiple states in neutrophils, a cell type often missed by single-cell methods in lung cancer. Critically, in the POPLAR/OAK clinical trials, Statescope identifies a combinatorial signature of effector CD8 + T cells and conventional dendritic cell states that together predict a striking survival benefit from immunotherapy. Collectively, Statescope transforms deconvolution into a versatile discovery platform, enabling deeper biological and clinical insights from widely available bulk multi-omics data.