Adaptation to ecologically contrasting niches can lead to the formation of new species. Theoretically, this process of ecological speciation can be driven by pleiotropic “magic traits” that genetically link natural and sexual selection. To qualify as a true magic trait, the pleiotropic function of a gene must be reflected in biologically relevant mechanisms underlying both local adaptation and mate choice. The immune genes of the major histocompatibility complex (MHC) contribute to parasite resistance and also play a major role in sexual selection. Hence, the MHC may encode a candidate magic trait. Using diverging 3-spined stickleback populations from a connected lake–river habitat, we show with mate choice experiments in a flow channel that polymorphic MHC genes probably underlie assortative mating with respect to particular habitat-adapted ecotypes, potentially resulting in reproductive isolation. By manipulating olfactory cues in controlled experiments, we show that female sticklebacks employ MHC-dependent male olfactory signals to select mates with which they can achieve a habitat-specific MHC gene structure that optimally protects their offspring against local parasites. By using MHC-based olfactory signals, females thus select individuals of their own population as mates. Our results demonstrate how mate choice and parasite resistance may be functionally linked. These findings suggest that MHC genes are pleiotropic and encode a true magic trait of biologically significant effect.