Most studies of heterozygosity-fitness correlations (HFCs) in natural populations relate to fitness traits expressed early in life, whereas traits that are often more difficult to measure such as longevity and adult body size remain elusive. Teeth provide a window on an individual's life history, allowing the reliable estimation of both age and body size. Consequently, we collected paired upper canine teeth and tissue samples from 84 adult male Antarctic fur seals Arctocephalus gazella that died of natural causes at Bird Island, South Georgia. Tooth size is a good predictor of skull and body size both within and across taxa, and we similarly find a strong relationship with skull size in our species. In turn, tooth size is itself predicted strongly by genetic heterozygosity estimated using 9 microsatellites. With only 9 loci, the exact mechanisms involved remain unclear, although the observed pattern appears largely attributable to a small subset of loci, suggesting that associative overdominance rather than inbreeding depression provides the proximate mechanism. In addition, locating these markers in the dog genome reveals proximity to genes involved with fat metabolism and growth. Our study illustrates how canine teeth, and potentially other structures such as tympano-periotic bone, waxy inner earplugs, or otoliths, may be used to explore links between genetic variation and important life-history traits in free-ranging vertebrate populations.