Cancer progression is an evolutionary process undergoing stringent immune selection. However, recent studies have revealed that certain tumors undergo neutral evolution following the malignant transformation. Here, we propose negative frequency-dependent selection (or NFDS), where the immune response against cancer cells depends on the clonality of neoantigens, can lead to an immunogenic landscape that is similar to neutral evolution. With a stochastic model of NFDS, we demonstrated that NFDSpromotes early immune evasion in hypermutable tumors, leading to neutral-like evolutionary dynamics with high antigenic heterogeneity and worse response to immune checkpoint blockade (ICB) therapy. Our model also revealed that NFDSis characterized by a negative association between average clonality and total burden of neoantigens. Indeed, NFDS was validated with whole-exome sequencing datasets (357 tumor samples from 275 patients) from four melanoma cohorts with ICB therapy. Altogether, our study provides the first quantitative evidence supporting the theory of NFDS in immune-driven cancer evolution. These findings highlight the critical role of NFDS theory in devising more efficient and predictive immunotherapies.