Cycads, unlike modern wind-pollinated conifers and Ginkgo, are unusual in that they are an ancient group of gymnosperms pollinated by insects [1-3]. Although it is well documented that cycads were diverse and abundant during the mid-Mesozoic, little is known about their biogeography and pollination before the rise of angiosperms. Direct fossil evidence illuminating the evolutionary history of cycads is extremely rare [4, 5]. Here we report a specialized beetle-mediated pollination mode from the mid Cretaceous of Myanmar, wherein a new boganiid beetle, Cretoparacucujus cycadophilus, with specialized pollen-feeding adaptations in its mouthparts and legs, was associated with many pollen grains of Cycadopites. Phylogenetic analyses indicate Cretoparacucujus as a sister group to the extant Australian Paracucujus, which pollinate the cycad Macrozamia riedlei. Our discovery, along with the current disjunct distribution of related beetle-herbivore (tribe Paracucujini) and cycad-host (tribe Encephalarteae) pairs in South Africa and Australia, indicate a probable ancient origin of beetle pollination of cycads at least in the Early Jurassic, long before angiosperm dominance and the radiation of flowering-plant pollinators later in the Cretaceous.