The genes of the major histocompatibility complex are the most polymorphic genes in vertebrates, with more than 1,000 alleles described in human populations. How this polymorphism is maintained, however, remains an evolutionary puzzle. Major histocompatibility complex genes have a crucial function in the adaptive immune system by presenting parasite-derived antigens to T lymphocytes. Because of this function, varying parasite-mediated selection has been proposed as a major evolutionary force for maintaining major histocompatibility complex polymorphism. A necessary prerequisite of such a balancing selection process is rapid major histocompatibility complex allele frequency shifts resulting from emerging selection by a specific parasite. Here we show in six experimental populations of sticklebacks, each exposed to one of two different parasites, that only those major histocompatibility complex alleles providing resistance to the respective specific parasite increased in frequency in the next host generation. This result demonstrates experimentally that varying parasite selection causes rapid adaptive evolutionary changes, thus facilitating the maintenance of major histocompatibility complex polymorphism.