Co-evolutionary relationships of plants and fungi are of great importance for the phylogeny of both groups. Nyssa was widely distributed in the northern hemisphere during the Cenozoic. Extant species of Nyssa exhibit a disjunct distribution between eastern North America, Central America and East Asia. Here, a new species, Nyssa nanningensis Xu & Jin, is described based on fruit endocarps from the upper Oligocene Yongning Formation of the Nanning Basin, South China. This new fossil record of Nyssa expands the known palaeogeographical distribution of the genus to the low latitudes of East Asia. Associated fossil fungal fruiting bodies on Nyssa endocarps are assigned to the new fossil genus and species, Yongnicta nyssae Tobias & Maslova. This new genus is similar to some members of extant wood destructor taxa Coronophorales and Amphisphaeriales (Sordariomycetes, Ascomycota). About 3% of the Nyssa endocarps studied were affected by Yongnicta nyssae. Low frequency of fruit damage indicates that endocarps could be released from mesocarps by animals eating fleshy parts of fruits, making them potentially available to wood-destroying fungi.