Few studies have addressed the evolutionary history of tree species from African savannahs at large geographic scales, particularly in the southern hemisphere (Zambezian region). Afzelia (Fabaceae: Caesalpinioideae) contains economically important timber species, including two species widely distributed in African savannahs: A. africana in the Sudanian region and A. quanzensis in the Zambezian region. To characterize the population genetic diversity and structure of these two species across their distribution ranges, we used nuclear microsatellites (simple sequence repeats, SSRs) and genotyping-by-sequencing (GBS) markers. Six SSR loci were genotyped in 241 A. africana and 113 A. quanzensis individuals, while 2,800 and 3,841 high-quality single nucleotide polymorphisms (SNPs) were identified in 30 A. africana and 12 A. quanzensis individuals, respectively. Both species appeared to be outcrossing (selfing rate ~ 0%). The spatial genetic structure was consistent with isolation-by-distance expectations based on both SSR and SNP data, suggesting that gene dispersal is spatially restricted in both species (bLd (SSR)= −0.005 and −0.007 and bLd (SNP)= −0.008 and −0.006 for A. africana and A. quanzensis, respectively). Bayesian clustering of SSR genotypes failed to identify genetic structure within species. In contrast, SNP data resolved intraspecific genetic clusters in both species, illustrating the higher resolving power of GBS at shallow levels of divergence. However, the clusters identified by SNPs revealed low levels of differentiation and no clear geographical entities. These results suggest that, although gene flow has been restricted over short distances in both species, populations have remained connected throughout the large, continuous Savannah landscapes. The absence of clear phylogeographic discontinuities, also found in a few other African savannah trees, indicates that their distribution ranges have not been significantly fragmented during past climate changes, in contrast to patterns commonly found in African rainforest trees.