Red Queen host-parasite co-evolution can drive adaptations of immune genes by positive selection that erodes genetic variation (Red Queen arms race) or results in a balanced polymorphism (Red Queen dynamics) and 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 by analysing the major histocompatibility complex (MHC) in guppies (Poecilia reticulata and P. obscura) and swamp guppies (Micropoecilia picta). Sub-functionalisation 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.