Red Queen host-parasite co-evolution can drive adaptations of immune-genes by positive selection that erodes genetic variation (Red Queen Arms Race), or result in a balanced polymorphism (Red Queen Dynamics) and the long-term preservation of genetic variation (trans-species polymorphism). These two Red Queen processes are opposite extremes of the co-evolutionary spectrum. Here we show that both Red Queen processes can operate simultaneously, analyzing the Major Histocompatibility Complex (MHC) in guppies (Poecilia reticulata and P. obscura), and swamp guppies (Micropoecilia picta). Sub-functionalization of MHC alleles into “supertypes” explains how polymorphisms persist during rapid host-parasite co-evolution. Simulations show the maintenance of supertypes as balanced polymorphisms, consistent with Red Queen Dynamics, whereas alleles within supertypes are subject to positive selection in a Red Queen Arms Race. Building on the Divergent Allele Advantage hypothesis, we show that functional aspects of allelic diversity help to elucidate the evolution of polymorphic genes involved in Red Queen co-evolution.