Paullinia L. is a genus of c. 220 mostly Neotropical forest-dwelling lianas that display a wide diversity of fruit morphologies. Paullinia resembles other members of the Paullinieae tribe in being a climber with stipulate compound leaves and paired inflorescence tendrils. However, it is distinct in having capsular fruits with woody, coriaceous, or crustaceous pericarps. While consistent in this basic plan, the pericarps of Paullinia fruits are otherwise highly variable—in some species they are winged, whereas in others they are without wings or covered with spines. With the exception of the water-dispersed indehiscent spiny fruits of some members of Paullinia sect. Castanella, all species are dehiscent, opening their capsules while they are still attached to the branch, to reveal arillate animal-dispersed seeds. Here we present a molecular phylogeny of Paullinia derived from 11 molecular markers, including nine newly-developed single-copy nuclear markers amplified by microfluidics PCR. This is the first broadly sampled molecular phylogeny for the genus. Paullinia is supported as monophyletic and is sister to Cardiospermum L., which together are sister to Serjania Mill + Urvillea Kunth. We apply this novel phylogenetic hypothesis to test previous infrageneric classifications and to infer that unwinged fruits represent the ancestral condition, from which there were repeated evolutionary transitions and reversals. However, because the seeds of both winged and unwinged fruits are dispersed by animals, we conclude that the repeated transitions in fruit morphology may relate to visual display strategies to attract animal dispersers, and do not represent transitions to wind dispersal.