Polyandry and post-copulatory sexual selection provide opportunities for the evolution of female differential sperm selection. Here, we examined the influence of variation in major histocompatibility (MH) class I allelic composition upon sperm competition dynamics in Atlantic salmon. We ran in vitro fertilization competitions that mimicked the gametic microenvironment, and replicated a paired-male experimental design that allowed us to compare differences in sperm competition success among males when their sperm compete for eggs from females that were genetically either similar or dissimilar at the MH class I locus. Concurrently, we measured variation in spermatozoal traits that are known to influence relative fertilization success under these conditions. Contrary to the findings demonstrating mechanisms that promote MH complex heterozygosity, our results showed that males won significantly greater relative fertilization success when competing for eggs from genetically similar females at the MH class I. This result also showed covariation with the known influences of sperm velocity on relative fertilization success. We discuss these unexpected findings in relation to sperm-egg recognition and hybridization avoidance mechanisms based upon immunogenetic variation.