Acacia senegal (L.) Willd. is the main species producing the internationally traded gum arabic. Genetic studies of this species are rare and until now the chromosome number was thought to be diploid (2n02x026). Here, using chromosome number counting, we demonstrate for the first time that tetraploids (2n04x052) also occur in A. senegal. Nuclear and chloroplast microsatellite markers were used to estimate and compare genetic variation within this newly described polyploidy complex in the Sudano- Sahelian region in Africa. Genetic diversity was higher in diploids, suggesting that the formation of tetraploids is recent and that mutation-drift equilibrium has not yet been reached. The two cytotypes do not have the same genetic structure and are genetically differentiated. Among tetraploids, populations are greatly differentiated and do not share the same chlorotypes. Based on these results, we discuss recurrent formation of tetraploids from different diploid progenitors across the distribution range of A. senegal in the Sudano-Sahelian zone.