Paganuccia is described as a new genus of Rubiaceae, only known so far from two collections from the continental dunes in the Sao Francisco River basin, Bahia, north-eastern Brazil. The morphological and molecular phylogenetic analyses based on nuclear (ETS, ITS) and plastid (atpB-rbcL, petD, rps16, trnL-trnF) sequence data, support the recognition of a new genus within the Spermacoce clade (tribe Spermacoceae). Paganuccia is one of several well-supported lineages, still largely unresolved with respect to each other. We considered that its isolated position in combination with the unique set of morphological character states and biogeographic evidence can fully support its recognition as a new genus. We have provided a formal description of Paganuccia, including SEM observations of the fruit, pollen, and inflorescence structure, together with a distribution map and comments on its conservation. Additionally, the new genus is compared with the other climbing taxa in the tribe, and a key for all the genera of the Spermacoceae in the Americas is provided.