The phylogeny of Celastraceae tribe Celastreae, which includes about 350 species of trees and shrubs in 15 genera, was inferred in a simultaneous analysis of morphological characters together with nuclear (ITS and 26S rDNA) and plastid (matK, trnL-F) genes. A strong correlation was found between the geography of the species sampled and their inferred relationships. Species of Maytenus and Gymnosporia from different regions were resolved as polyphyletic groups. Maytenus was resolved in three lineages (New World, African, and Austral-Pacific), while Gymnosporia was resolved in two lineages (New World and Old World). Putterlickia was resolved as nested within the Old World Gymnosporia. Catha edulis (qat, khat) was resolved as sister to the clade of Allocassine, Cassine, Lauridia, and Maurocenia. Gymnosporia cassinoides, which is reportedly chewed as a stimulant in the Canary Islands, was resolved as a derived member of Gymnosporia and is more closely related to Lydenburgia and Putterlickia than it is to Catha. Therefore, all eight of these genera are candidates for containing cathinone- and/or cathine-related alkaloids.