The major histocompatibility complex (MHC) is crucial to the adaptive immune response of vertebrates and is among the most polymorphic gene families known. Its high diversity is usually attributed to selection imposed by fast-evolving pathogens. Pathogens are thought to evolve to escape recognition by common immune alleles, and, hence, novel MHC alleles, introduced through mutation, recombination, or gene flow, are predicted to give hosts superior resistance. Although this theoretical prediction underpins host–pathogen “Red Queen” coevolution, it has not been demonstrated in the context of natural MHC diversity. Here, we experimentally tested whether novel MHC variants (both alleles and functional “supertypes”) increased resistance of guppies (Poecilia reticulata) to a common ectoparasite (Gyrodactylus turnbulli). We used exposure-controlled infection trials with wild-sourced parasites, and Gyrodactylus-naïve host fish that were F2 descendants of crossed wild populations. Hosts carrying MHC variants (alleles or supertypes) that were new to a given parasite population experienced a 35–37% reduction in infection intensity, but the number of MHC variants carried by an individual, analogous to heterozygosity in single-locus systems, was not a significant predictor. Our results provide direct evidence of novel MHC variant advantage, confirming a fundamental mechanism underpinning the exceptional polymorphism of this gene family and highlighting the role of immunogenetic novelty in host–pathogen coevolution.