The genus Vachellia is named after Rev. George Harvey Vachell (1789–1839), who was a chaplain to the British East India Company in Macau and a plant collector in China. The species is named for its place of origin, sekhukhuniensis meaning ‘from Sekhukhuneland’. The genus Vachellia contains 163 species, 83 are found in Africa, Madagascar and the Mascarene Islands, 52 in the Americas, 32 in Asia, and 9 in Australia and the Pacific islands. Thorn trees are members of the legume family, Fabaceae, ranked the third largest family among angiosperms after the orchid family (Orchidaceae) and the daisy family (Asteraceae), consisting of more than 700 genera and 20 000 species of trees, shrubs, vines and herbs distributed worldwide.

This species was first collected by W.F. Stuurman in 1972, but remained unidentified until P.J.H. Hurter went looking for plants that matched Stuurman’s specimen, which were found in 2003. Field observations and a comparative morphological analysis confirmed it to be a new species, which was formally described in 2004 as Acacia sekhukuniensis. DNA studies done on the genus Acacia showed that the approximately 1 200 species that were grouped under the genus, were not all descended from the same common ancestor, resulting in the genus being split into a number of new genera. The name Acacia was conserved for the Australian species, despite it being the original name for an African species and despite the decision being challenged by African botanists, and in 2013 all the African acacias were transferred to one of two new genera: Vachellia (those with paired stipular spines at the nodes and no prickles) or Senegalia (those with no stipular spines and often with prickles).