The major histocompatibility complex (MHC) is a source of unique individual odors that influence individual recognition, mating preferences, nesting behavior and selective block of pregnancy in animals. Such phenomena have been difficult to study in humans, because the human leukocyte antigen (HLA, human MHC) loci are the most polymorphic loci in the human genome, with the potential to generate millions of unique combinations of genotypes. In addition, high variability in background odors, encoded by the rest of the genome and influenced by cultural practices, contribute to a low signal-to-noise ratio that could mask HLA-based olfactory cues. Here we show that women can detect differences of one HLA allele among male odor donors with different MHC genotypes. Notably, the mechanism for a woman's ability to discriminate and choose odors is based on HLA alleles inherited from her father but not her mother. The parents' HLA alleles that she does not inherit show no relationship with odor choice, despite exposure to these HLA-encoded odors throughout her life. Our data indicate that paternally inherited HLA-associated odors influence odor preference and may serve as social cues.