During progression from carcinoma in situ to an invasive tumor, the immune system is engaged in complex sets of interactions with various tumor cells. Tumor cell plasticity alters disease trajectories via epithelial-to-mesenchymal transition (EMT). Several of the same pathways that regulate EMT are involved in tumor-immune interactions, yet little is known about the mechanisms and consequences of crosstalk between these regulatory processes. Here we introduce a multiscale evolutionary model to describe tumor-immune-EMT interactions and their impact on epithelial cancer progression from in situ to invasive disease. Through simulation of patient cohorts in silico, the model predicts that a controllable region maximizes invasion-free survival. This controllable region depends on properties of the mesenchymal tumor cell phenotype: its growth rate and its immune-evasiveness. In light of the model predictions, we analyze EMT-inflammation-associated data from The Cancer Genome Atlas, and find that association with EMT worsens invasion-free survival probabilities. This result supports the predictions of the model, and leads to the identification of genes that influence outcomes in bladder and uterine cancer, including FGF pathway members. These results suggest new means to delay disease progression, and demonstrate the importance of studying cancer-immune interactions in light of EMT.