Kosteletzkya s.s. is a genus of 17 species (excluding the endemic species of Madagascar), found in the New World, continental Africa, Madagascar, and Southeast Asia. Recent chromosome counts revealed diploid, tetraploid, and hexaploid species. To estimate the history of the genus, we sequenced nuclear and plastid loci for nearly all Kosteletzkya spp., in the majority of cases, with multiple accessions per species. The African species form a paraphyletic grade relative to a New World clade. Polyploidy has occurred only in some African species, resulting in the relatively ancient formation of one putative autotetraploid species (K. semota), one recent allotetraploid species (K. borkouana), two relatively ancient allotetraploid species (K. begoniifolia and K. rotundalata) and one recent allohexaploid species (K. racemosa). Our inferences regarding the hypothesized parentage of the polyploids mostly corroborate previous work based on chromosome-pairing patterns in artificial hybrids, highlighting the utility of these complementary data sources.