The Hymenodictyeae-Naucleeae clade is a predominantly Paleotropical group with 220 species in 28 genera. The phylogenetic relationships and generic limits within Naucleeae have previously been assessed using combined molecular-morphological data, however the status of some genera remains questionable. The evolutionary relationships within Hymenodictyeae have never been investigated before. We performed phylogenetic analyses of the Hymenodictyeae-Naucleeae clade using nuclear [nrETS; nrITS] and chloroplast [ndhF; rbcL; rps16; trnT-F] data and a large sampling of both tribes. Our study supports the monophyly of the tribes, all subtribes of Naucleeae (Adininae, Breoniinae, Cephalanthinae, Corynantheinae, Mitragyninae, Naucleinae, and Uncariinae), and the Hymenodictyeae genera Hymenodictyon and Paracorynanthe. In Naucleeae, the monotypic genera Adinauclea, Metadina, and Pertusadina are nested within Adina, Mitragyna within Fleroya, Ludekia, Myrmeconauclea, and Ochreinauclea within Neonauclea, and Burttdavya and Sarcocephalus within Nauclea. Corynanthe and Pausinystalia are mutually paraphyletic. We provisionally maintain the current generic status of Neonauclea and its allied genera, pending further study. In sum, we recognize 17 genera in Naucleeae: Adina s.l., Breonadia, Breonia, Cephalanthus, Corynanthe s.l., Diyaminauclea, Gyrostipula, Janotia, Khasiaclunea, Ludekia, Mitragyna s.l., Myrmeconauclea, Nauclea s.l., Neolamarckia, Neonauclea, Ochreinauclea, and Uncaria. Five new combinations were made: Adina euryncha, Adina malaccensis, Corynanthe lane-poolei subsp. iturense, Corynanthe talbotii, and Nauclea nyasica.