Paullinieae are a diverse group of tropical and subtropical climbing plants that belong to the soapberry family (Sapindaceae). The six genera in this tribe make up approximately one-quarter of the species in the family, but a sparse fossil record limits our understanding of their diversification. Here, we provide the first description of anatomically preserved fossils of Paullinieae and we re-evaluate other macrofossils that have been attributed to the tribe. We identified permineralized fossil roots in collections from the lower Miocene Cucaracha Formation where it was exposed along the Culebra Cut of the Panama Canal. We prepared the fossils using the cellulose acetate peel technique and compared the anatomy with that of extant Paullinieae. The fossil roots preserve a combination of characters found only in Paullinieae, including peripheral secondary vascular strands, vessel dimorphism, alternate intervessel pitting with coalescent apertures, heterocellular rays, and axial parenchyma strands of 2-4 cells, often with prismatic crystals. We also searched the paleontological literature for other occurrences of the tribe. We re-evaluated leaf fossils from western North America that have been assigned to extant genera in the tribe by comparing their morphology to herbarium specimens and cleared leaves. The fossil leaves that were assigned to Cardiospermum and Serjania from the Paleogene of western North America are likely Sapindaceae; however, they lack diagnostic characters necessary for inclusion in Paullinieae and should be excluded from those genera. Therefore, the fossils described here as Ampelorhiza heteroxylon gen. et sp. nov. are the oldest macrofossil evidence of Paullinieae. They provide direct evidence of the development of a vascular cambial variant associated with the climbing habit in Sapindaceae and provide strong evidence of the diversification of crown-group Paullinieae in the tropics by 18.5-19 million years ago.