New compression leaf material of Ceratozamia (Zamiaceae) has been recognised in the European Cenozoic. A leaflet of Ceratozamia floersheimensis (Engelhardt) Kvaček was recovered among unidentified material from the Oligocene of Trbovlje, former Trifail, Slovenia, housed in old collections of the Austrian Geological Survey, Vienna. It is similar in morphology and epidermal anatomy to other specimens previously studied from the lower Oligocene of Flörsheim, Germany and Budapest, Hungary. A fragmentary leaflet assigned to C. hofmannii Ettingsh. was recovered in the uppermost part of the Most Formation (Most Basin in North Bohemia, Czech Republic) and dated by magnetostratigraphy and cyclostratigraphy to CHRON C5Cn.3n, that is, the latest early Miocene. It yielded excellently preserved epidermal structures, permitting confirmation of the generic affinity and a more precise comparison with this lower Miocene species previously known from Austria (Münzenberg, Leoben Basin) and re-investigated earlier. Both the Oligocene and Miocene populations of Ceratozamia are based on isolated disarticulated leaflets matching some living representatives in the size and slender form of the leaflets. Such ceratozamias thrive today in extratropical areas near the present limits of distribution of the genus along the Sierra Madre Orientale in north-eastern Mexico, in particular C. microstrobila Vovides & J.D. Rees and others of the C. latifolia complex, as well as C. hildae G.P. Landry & M.C. Wilson (“bamboo cycad”). The occurrence of Ceratozamia suggests subtropical to warm-temperate, almost frostless climate and a high amount of precipitation. The accompanied fossil vegetation of both species corresponds well with the temperature regime. While the Oligocene species in Hungary probably thrived under sub-humid conditions, the remaining occurrences of fossil Ceratozamia were connected with humid evergreen to mixed-mesophytic forests.