Senegalia comprises 219 species distributed in tropical and subtropical regions of North and South America, Africa, Asia and Australia. Two sections are currently recognised within Senegalia and these are most readily distinguished by the differences in disposition of their cauline prickles, i.e. sect. Senegalia with prickles at or near leaf nodes and sect. Monacanthea with mostly internodal prickles. Previous phylogenetic studies, based primarily on small numbers of plastid DNA loci, found Senegalia to be monophyletic with two large subclades corresponding to the sections. Here, we present new phylogenomic evidence from 997 single-copy nuclear gene sequences for a small, but representative set of species. These new analyses show that Senegalia is non-monophyletic, but instead, forms a grade that is paraphyletic with respect to the remainder of the ingoid clade (i.e. Ingeae + Acacia s.s. + Acaciella), comprising two well-supported subclades most likely representing the same clades as found in previous phylogenetic studies of the genus and, interspersed between these, a third, moderately supported clade, comprising the genera Mariosousa, Pseudosenegalia and Parasenegalia. In marked contrast to the nuclear phylogeny, the two Senegalia clades are sister groups in the plastid phylogeny, based on analyses of 72 chloroplast genes, rendering the genus monophyletic, based on plastid data alone. We discuss this new evidence that Senegalia is non-monophyletic in relation to the marked cytonuclear discordance, high gene tree conflict and lack of resolution across this senegalioid grade and review the consistency of the key morphological characters distinguishing the two sections of Senegalia. We conclude that it is likely that Senegalia will need to be split into two (or possibly more) genera: a re-circumscribed Senegalia s.s. that corresponds to the existing Senegalia sect. Senegalia plus the S. ataxacantha group (Senegalia sect. Monacanthea s.s.; future studies may show that this group warrants generic status) and a new genus corresponding to the remainder of sect. Monacanthea (here designated as Senegalia sect. Monacanthea p.p.). However, re-delimiting Senegalia now would be premature given that the key morphological characters are not fully congruent with the two sections and pending denser phylogenetic sampling of taxa. A judiciously selected list of critical taxa is presented to facilitate future phylogenomic studies. Finally, we discuss the identity of Albizia leonardii, which is also placed in this senegalioid grade in these new phylogenomic analyses and place it in synonymy with Parasenegalia vogeliana.