In Europe, fossil fruits and seeds of Rhodoleia (Hamamelidaceae) have been described from the Upper Cretaceous to the Miocene, whereas no fossil record of Rhodoleia has been reported in Asia, where the modern species occur. Herein, 21 fossil leaves identified as Rhodoleia tengchongensis sp. nov. are described from the Upper Pliocene of Tengchong County, Yunnan Province, Southwest China. The fossils exhibit elliptic lamina with entire margins, simple brochidodromous major secondary veins, mixed percurrent intercostal tertiary veins, and looped exterior tertiaries. The leaf cuticle is characterized by pentagonal or hexagonal cells, stellate multicellular trichomes, and paracytic stomata. The combination of leaf architecture and cuticular characteristics suggests that the fossil leaves should be classified into the genus Rhodoleia. The fossil distributions indicate that the genus Rhodoleia might originate from Central Europe, and that migrated to Asia prior to the Late Pliocene. Additionally, insect damage is investigated, and different types of damage, such as hole feeding, margin feeding, surface feeding, and galling, are observed on the thirteen fossil leaves. Based on the damage frequencies for the fossil and extant leaves, the specific feeding behavior of insects on Rhodoleia trees appears to have been established as early as the Late Pliocene. The high occurrence of Rhodoleia insect herbivory may attract the insect-foraging birds, thereby increasing the probability of pollination.