Behavior and genetic structure are intimately related: mating patterns and patterns of movement between groups or populations influence the movement of genetic variation across the landscape and from one generation to the next. In hybrid zones, the behavior of the hybridizing taxa can also have an important impact on the incidence and outcome of hybridization events. Hybridization between yellow baboons and anubis baboons has been well-documented in the Amboseli basin of Kenya, where more anubis-like individuals tend to experience maturational and reproductive advantages. However, it is unknown whether these advantages are reflected in the genetic structure of populations surrounding this area. Here, we used nuclear microsatellite genotype data to evaluate the geographic structure and composition of baboon populations in southern Kenya, up to the border of Tanzania. Our results indicate that, unlike for mitochondrial DNA, microsatellite-based measures of genetic structure are in concordance with phenotypically based taxonomic distinctions, and that the currently active hybrid zone is relatively narrow. Interestingly, isolation with migration analysis revealed asymmetric gene flow in this region from anubis populations into yellow populations, in support of the anubis-biased phenotypic advantages observed in Amboseli. Populations that are primarily yellow but that are the recipients of anubis gene flow exhibit higher levels of genetic diversity than yellow populations far from the introgression front. Our results support previous work that indicates a long history of hybridization and male-mediated genetic introgression among East African baboons. In particular, it suggests that anubis baboons are in the process of gradual range expansion into the historic range of yellow baboon populations, a pattern that could be mechanistically explained by behavioral and life history advantages that correlate with anubis ancestry.