An increasing number of studies test the idea that females increase offspring fitness by biasing fertilization in favour of genetically compatible partners; however, few have investigated or controlled for corresponding preferences in males. Here, we experimentally test whether male red junglefowl, Gallus gallus, prefer genetically compatible females, measured by similarity at the major histocompatibility complex (MHC), a key gene complex in vertebrate immune function. Theory predicts that because some degree of MHC heterozygosity favours viability, individuals should prefer partners that carry MHC alleles different from their own. While male fowl showed no preference when simultaneously presented with an MHC-similar and an MHC-dissimilar female, they showed a ‘cryptic’ preference, by allocating more sperm to the most MHC-dissimilar of two sequentially presented females. These results provide the first experimental evidence that males might respond to the MHC similarity of a female through differential ejaculate expenditure. By revealing that cryptic male behaviours may bias fertilization success in favour of genetically compatible partners, this study demonstrates the need to experimentally disentangle male and female effects when studying preferences for genetically compatible partners.