Although clonal neo-antigen burden is associated with improved response to immune therapy, the functional basis for this remains unclear. Here we study this question in a novel controlled mouse melanoma model that enables us to explore the effects of intra-tumor heterogeneity (ITH) on tumor aggressiveness and immunity independent of tumor mutational burden. Induction of UVB-derived mutations yields highly aggressive tumors with decreased anti-tumor activity. However, single-cell-derived tumors with reduced ITH are swiftly rejected. Their rejection is accompanied by increased T cell reactivity and a less suppressive microenvironment. Using phylogenetic analyses and mixing experiments of single-cell clones, we dissect two characteristics of ITH: the number of clones forming the tumor and their clonal diversity. Our analysis of melanoma patient tumor data recapitulates our results in terms of overall survival and response to immune checkpoint therapy. These findings highlight the importance of clonal mutations in robust immune surveillance and the need to quantify patient ITH to determine the response to checkpoint blockade.