The impact of the Pleistocene climate oscillations on the structure of biodiversity in tropical regions remains poorly understood. In this study, the forest refuge theory is examined at the molecular level in Milicia excelsa, a dioecious tree with a continuous range throughout tropical Africa. Eight nuclear microsatellites (nSSRs) and two sequences and one microsatellite from chloroplast DNA (cpDNA) showed a deep divide between samples from Benin and those from Lower Guinea. This suggests that these populations were isolated in separate geographical regions, probably for several glacial cycles of the Pleistocene, and that the nuclear gene pools were not homogenized despite M. excelsa's wind-pollination syndrome. The divide could also be related to seed dispersal patterns, which should be largely determined by the migration behaviour of M. excelsa's main seed disperser, the frugivorous bat Eidolon helvum. Within Lower Guinea, a north-south divide, observed with both marker types despite weak genetic structure (nSSRs: F(ST) = 0.035, cpDNA: G(ST) = 0.506), suggested the existence of separate Pleistocene refugia in Cameroon and the Gabon/Congo region. We inferred a pollen-to-seed dispersal distance ratio of c.1.8, consistent with wide-ranging gene dispersal by both wind and bats. Simulations in an Approximate Bayesian Computation framework suggested low nSSR and cpDNA mutation rates, but imprecise estimates of other demographic parameters, probably due to a substantial gene flow between the Lower Guinean gene pools. The decline of genetic diversity detected in some Gabonese populations could be a consequence of the relatively recent establishment of a closed canopy forest, which could negatively affect M. excelsa's reproductive system.