Many models of sex-biased dispersal predict that the direction of sex-bias depends upon a species' mating system. In agreement with this, almost all polygynous mammals show male-biased dispersal whereas largely monogamous birds show female-biased dispersal (FBD). The hamadryas baboon (Papio hamadryas hamadryas) is polygynous and so dispersal is predicted to be male biased, as is found in all other baboon subspecies, but there are conflicting field data showing both female and male dispersal. Using 19 autosomal genetic markers genotyped in baboons from four Saudi Arabian populations, we found strong evidence for FBD in post-dispersal adults but not, as expected, in pre-dispersal infants and young juveniles, when we compared male and female: population structure (F(st)), inbreeding (F(is)), relatedness (r), and the mean assignment index (mAIc). Furthermore, we found evidence for female-biased gene flow as population genetic structure (F(st)), was about four times higher for the paternally inherited Y, than for either autosomal markers or for maternally inherited mtDNA. These results contradict the direction of sex-bias predicted by the mating system and show that FBD has evolved recently from an ancestral state of male-biased dispersal. We suggest that the cost-benefit balance of dispersal to males and females is tightly linked to the unique hierarchical social structure of hamadryas baboons and that dispersal and social organization have coevolved.