Cyphostemma, with ca. 200 species, is the second-largest genus after Cissus in the grape family Vitaceae. Cyphostemma exhibits a high degree of morphological variation both between and within species that confounds species delimitation. Additional questions remain due to limited taxon sampling, original reference specimens damaged or lost and incomplete descriptions of taxa. Previous molecular studies, with limited taxon sampling, suggested three major clades corresponding to their distribution in continental Africa, Madagascar and Asia. However, deep relationships and biogeographic history within Cyphostemma remain unresolved. We conducted phylogenetic analysis and morphological character reconstruction of Cyphostemma using 91 newly assembled plastomes, with a focus on resolving complex taxonomic issues in Madagascar. Our results strongly support the Malagasy Cyphostemma as non-monophyletic for the first time. Biogeographic reconstructions reveal two independent dispersals from continental Africa to Madagascar. The first dispersal is dated to the Oligocene and has led to the diversification of species with pinnate leaves in Madagascar. The second dispersal is estimated to have occurred during the late Miocene and has given rise to the only species with digitate leaves in Madagascar. Ancestral state reconstructions reveal that several morphological innovations may have promoted adaptation of Cyphostemma to a diverse range of habitats in Madagascar. In particular, a group of species from southern Madagascar have evolved both succulent stems and leaves to cope with extreme aridification in this region. Finally, relationships within three species complexes from the “Sambirano domain”, the southern spiny forest-thicket and the northern limestone areas of Madagascar are clarified and four new taxa are proposed based on molecular and morphological evidence.