Gum arabic is an important international commodity produced by trees of Acacia senegal across Sahelian Africa, but documented results of breeding activities are limited. The objective of this study was to provide reliable estimates of quantitative genetic parameters in order to shed light on the breeding potential for improvement of gum yield and quality. For this purpose, we measured growth on 617 offspring from 60 open-pollinated trees after 18 years, and gum yield and quality based on two seasons, 18 and 19 years after establishment. Genotyping with eight microsatellite markers revealed that progenies consisted of both diploid and polyploid trees, and growth, gum yield, and gum quality varied substantially among ploidy level, populations, and progenies. Analysis of molecular variance and estimates of outcrossing rate supported that trees within open-pollinated families of diploids were half sibs, while the open-pollinated families of polyploids showed low variation within families. The difference in sibling relationship observed between ploidy levels complicated estimation of genetic parameters. However, based on the diploid trees, we conclude that heritability in gum arabic production is low to high with presence of high levels of additive genetic variation, although the genetic parameters could only be estimated with fairly high standard error. The findings suggest that improvement through breeding can increase the productivity of A. senegal substantially. However, the results also stress the importance of testing ploidy levels of selected material and use of genetic markers to qualify the assumptions in the quantitative genetic analysis.