Paleo-environmental data show that the distribution of African rain forests was affected by Quaternary climate changes. In particular, the Dahomey Gap (DG) – a 200 km wide savanna corridor currently separating the West African and Central African rain forest blocks and containing relict rain forest fragments – was forested during the mid-Holocene and possibly during previous interglacial periods, whereas it was dominated by open vegetation (savanna) during glacial periods. Genetic signatures of past population fragmentation and demographic changes have been found in some African forest plant species using nuclear markers, but such events appear not to have been synchronous or shared across species. To better understand the colonization history of the DG by rain forest trees through seed dispersal, the plastid genomes of two widespread African forest legume trees, Anthonotha macrophylla and Distemonanthus benthamianus, were sequenced in 47 individuals for each species, providing unprecedented phylogenetic resolution of their maternal lineages (857 and 115 SNPs, respectively). Both species exhibit distinct lineages separating three regions: 1. Upper Guinea (UG, i.e. the West African forest block), 2. the area ranging from the DG to the Cameroon volcanic line (CVL), and 3. Lower Guinea (LG, the western part of the Central African forest block) where three lineages co-occur. In both species, the DG populations (including southern Nigeria west of Cross River) exhibit much lower genetic diversity than UG and LG populations, and their plastid lineages originate from the CVL, confirming the role of the CVL as an ancient forest refuge. Despite the similar phylogeographic structures displayed by A. macrophylla and D. benthamianus, molecular dating indicates very contrasting ages of lineage divergence (UG diverged from LG since c. 7 Ma and 0.7 Ma, respectively) and DG colonization (probably following the Mid Pleistocene Transition and the Last Glacial Maximum, respectively). The stability of forest refuge areas and repeated similar forest shrinking/expanding events during successive glacial periods might explain why similar phylogeographic patterns can be generated over contrasting timescales.