Diospyros is a large genus of woody flowering plants with a predominantly subtropical and tropical modern distribution. Fossils attributed to Diospyros are mainly leaf impressions from Cretaceous and Cenozoic strata across the Northern Hemisphere. However, it is difficult to assign such fossils to Diospyros because genus-diagnostic leaf characteristics remain to be identified. Unequivocal fossil records of Diospyros are few, including staminate flowers with in situ pollen from the late Eocene of South Australia and dispersed pollen from Cenozoic strata in the Northern Hemisphere. Here, we investigated dispersed pollen and calyx remains from Miocene deposits of Denmark using a combined scanning electron/light microscopy approach. Tricolporate, relatively large pollen with lalongate pori and longbow-shaped colpi and a distinctive micro/nanorugulate exine ornamentation together with persistent 4-lobed flower calyces allow unambiguous identification of the genus. Based on the large size of the calyx, we describe a new fossil-species of Diospyros. Further, a review of the fossil pollen record of Diospyros shows that, in addition to the Australian record, the genus was present in South China, western North America and Europe during the Eocene and in East and South Africa and Central Asia during the Oligo-Miocene. Although still scanty, the pollen record can contribute vital information for time calibrated molecular phylogenies to resolve conflicting biogeographic inferences. A thorough description of the historical biogeography of Diospyros is still in its infancy. While we initiate such a study here, development of a comprehensive picture will require further studies of dispersed pollen grains with high taxonomic resolution.