PREMISE OF THE STUDY: Fossilized seeds similar to Cissus (Vitaceae) have been recognized from the Miocene of Kenya, though some were previously assigned to the Menispermaceae. We undertook a comparative survey of extant African Cissus seeds to identify the fossils and consider their implications for the evolution and biogeography of Cissus and for African early Miocene paleoenvironments. METHODS: Micro-computed tomography (µCT) and synchrotron-based X-ray tomographic microscopy (SRXTM) were used to study seed morphology and anatomy. Virtual taphonomy, using SRXTM data sets, produced digital fossils to elucidate seed taphonomy. Phylogenetic relationships within Cissus were reconstructed using existing and newly produced DNA sequences for African species. Paleobiology and paleoecology were inferred from African nearest living relatives. KEY RESULTS: The fossils were assigned to four new Cissus species, related to four modern clades. The fossil plants were interpreted as climbers inhabiting a mosaic of riverine woodland and forest to more open habitats. Virtual taphonomy explained how complex mineral infill processes concealed key seed features, causing the previous taxonomic misidentification. Newly sampled African species, with seeds most similar to the fossils, belong to four clades within core Cissus, two of which are early diverging. CONCLUSIONS: Virtual taphonomy, combined with X-ray imaging, has enabled recognition of the first fossil Cissus and Vitaceae from Africa. Early-divergent members of the core Cissus clade were present in Africa by at least the early Miocene, with an African origin suggested for the Cissus sciaphila clade. The fossils provide supporting evidence for mosaic paleoenvironments inhabited by early Miocene hominoids.