Antigen loss is a key mechanism how tumor cells escape from T-cell immunotherapy. Using a mouse model of melanoma we directly compared antigen downregulation by phenotypic adaptation with genetically hardwired antigen loss. Unexpectedly, genetic ablation of Pmel, the melanocyte differentiation antigen targeted by adoptively transferred CD8+ T-cells, impaired melanoma cell growth in untreated tumors due to competitive pressure exerted by the bulk wild-type population. This established an evolutionary scenario, where T-cell immunotherapy imposed a dynamic fitness switch on wild-type melanoma cells and antigen loss variants, which resulted in highly variable enrichment of the latter in recurrent tumors. Stochastic simulations by an individual-based continuous-time Markov process suggested variable fitness of subclones within the antigen loss variant population as the most likely cause, which was validated experimentally. In summary, we provide a framework to better understand how subclone heterogeneity in tumors influences immune selection of genetic antigen loss variants through stochastic events.