The evolutionary history of African savannah tree species is crucial for the management of their genetic resources. In this study, we investigated the phylogeography of Parkia biglobosa and its modeled distribution under past and present climate conditions. This tree species is very valued and widespread in West Africa, providing edible and medicinal products. A large sample of 1610 individuals from 84 populations, distributed across 12 countries in Western and Central Africa, were genotyped using 8 nuclear microsatellites. Individual-based assignments clearly distinguished 3 genetic clusters, extreme West Africa (EWA), center of West Africa (CWA), and Central Africa (CA). Overall, estimates of genetic diversity were moderate to high, with lower values for populations in EWA (allelic richness after rarefaction [AR] = 6.4, expected heterozygosity [HE] = 0.78, and observed heterozygosity [HO] = 0.7) and CA (AR = 5.9, HE = 0.67, and HO = 0.61) compared with populations in CWA (AR = 7.3, HE = 0.79, and HO = 0.75). The overall population differentiation was found to be moderate (FST = 0.09). A highly significant isolation by distance pattern was detected, with a marked phylogeographic signature suggesting possible effects of past climate and geographic barriers to migration. Modeling the potential distribution of the species showed a contraction during the last glaciations followed by expansion events. The exploratory approximate Bayesian computation conducted suggests a best-supported scenario in which the cluster CWA traced back to the ancestral populations and a first split between EWA and CWA took place about 160000 years before present (BP), then a second split divided CA and CWA, about 100000 years BP. However, our genetic data do not enable us to conclusively distinguish among a few alternative possible scenarios.