A large body of theoretical work suggests that analyses of variation at the maternally inherited mitochondrial (mt)DNA and the paternally inherited non-recombining portion of the Y chromosome (NRY) are a potentially powerful way to reveal the differing migratory histories of men and women across human societies. However, the few empirical studies comparing mtDNA and NRY variation and known patterns of sex-biased migration have produced conflicting results. Here we review some methodological reasons for these inconsistencies, and take them into account to provide an unbiased characterization of mtDNA and NRY variation in chimpanzees, one of the few mammalian taxa where males routinely remain in and females typically disperse from their natal groups. We show that patterns of mtDNA and NRY variation are more strongly contrasting in patrilocal chimpanzees compared with patrilocal human societies. The chimpanzee data we present here thus provide a valuable comparative benchmark of the patterns of mtDNA and NRY variation to be expected in a society with extremely female-biased dispersal.