House mice prefer mates genetically dissimilar at the major histocompatibility complex (MHC). The highly polymorphic MHC genes control immunological self/nonself recognition; therefore, this mating preference may function to provide "good genes" for an individual's offspring. However, the evidence for MHC-dependent mating preferences is controversial, and its function remains unclear. Here we provide a critical review of the studies on MHC-dependent mating preferences in mice, sheep, and humans and the possible functions of this behavior. There are three adaptive hypotheses for MHC-dependent mating preferences. First, MHC-disassortative mating preferences produce MHC-heterozygous offspring that may have enhanced immunocompetence. Although this hypothesis is not supported by tests of single parasites, MHC heterozygotes may be resistant to multiple parasites. Second, we propose that MHC-dependent mating preferences enable hosts to provide a "moving target" against rapidly evolving parasites that escape immune recognition (the Red Queen hypothesis). Such parasites are suspected to drive MHC diversity through rare-allele advantage. Thus, the two forms of parasite-mediated selection thought to drive MHC diversity, heterozygote and rare-allele advantage, will also favor MHC-dependent mating preferences. Finally, MHC-dependent mating preferences may also function to avoid inbreeding; a hypothesis consistent with other evidence that MHC genes play a role in kin recognition.