Sex differences in parasite load and immune responses are found across a wide range of animals, with females generally having lower parasite loads and stronger immune responses than males. Intrigued by these general patterns, we investigated if there was any sign of sex-specific selection on an essential component of adaptive immunity that is known to affect fitness, the major histocompatibility complex class I (MHC-I) genes, in a 20-year study of great reed warblers. Our analyses on fitness related to MHC-I diversity showed a highly significant interaction between MHC-I diversity and sex, where males with higher, and females with lower, MHC-I diversity were more successful in recruiting offspring. Importantly, mean MHC-I diversity did not differ between males and females, and consequently neither sex reached its MHC-I fitness optimum. Thus, there is an unresolved genetic sexual conflict over MHC-I diversity in great reed warblers. Selection from pathogens is known to maintain MHC diversity, but previous theory ignores that the immune environments are considerably different in males and females. Our results suggest that sexually antagonistic selection is an important, previously neglected, force in the evolution of vertebrate adaptive immunity, and have implications for evolutionary understanding of costs of immune responses and autoimmune diseases.