Cellular deconvolution algorithms virtually reconstruct tissue composition by analyzing the gene expression of complex tissues. We present the decision tree machine learning algorithm, Kassandra, trained on a broad collection of >9,400 tissue and blood sorted cell RNA profiles incorporated into millions of artificial transcriptomes to accurately reconstruct the tumor microenvironment (TME). Bioinformatics correction for technical and biological variability, aberrant cancer cell expression inclusion, and accurate quantification and normalization of transcript expression increased Kassandra stability and robustness. Performance was validated on 4,000 H&E slides and 1,000 tissues by comparison with cytometric, immunohistochemical, or single-cell RNA-seq measurements. Kassandra accurately deconvolved TME elements, showing the role of these populations in tumor pathogenesis and other biological processes. Digital TME reconstruction revealed that the presence of PD-1-positive CD8+ T cells strongly correlated with immunotherapy response and increased the predictive potential of established biomarkers, indicating that Kassandra could potentially be utilized in future clinical applications.