Hamilton and Zuk’s influential hypothesis of parasite-mediated sexual selection proposes that exaggerated secondary sexual ornaments indicate a male’s additive genetic immunity to parasites. However, genetic correlates of ornamentation and immunity have rarely been explicitly identified. Evidence supporting Hamilton and Zuk’s hypothesis has instead been gathered by looking for positive phenotypic correlations between ornamentation and immunity; such correlations are assumed to reflect causal, additive relationships between these traits. We show that in song sparrows, Melospiza melodia, a male’s song repertoire size, a secondary sexual trait, increased with his cell-mediated immune response (CMI) to an experimental challenge. However, this phenotypic correlation could be explained because both repertoire size and CMI declined with a male’s inbreeding level. Repertoire size therefore primarily indicated a male’s relative heterozygosity, a non-additive genetic predictor of immunity. Caution may therefore be required when interpreting phenotypic correlations as support for Hamilton and Zuk’s additive model of sexual selection. However, our results suggest that female song sparrows choosing males with large repertoires would on average acquire more outbred and therefore more heterozygous mates. Such genetic dominance effects on ornamentation are likely to influence evolutionary trajectories of female choice, and should be explicitly incorporated into genetic models of sexual selection.