Global climate during the Mesozoic and early Cenozoic is thought to have been warmer than at present, but there is debate about winter temperatures. Paleontological data indicate mild temperatures even at high latitudes and in mid-latitude continental interiors, whereas computer simulations of continental paleoclimates produce winter temperatures closer to modern levels. Foliar physiognomy and floristic composition of 23 Eocene floras from the interior of North America and Australia indicate cold month means generally >2 °C, even where the mean annual temperature (MAT) was <15 °C. Reconstructed Eocene latitudinal gradients of MAT are curvilinear but are about 0.4 °C per 1° of latitude in continental interiors at mid-latitudes, much less than the 0.8–1.0 °C per 1° of latitude observed in eastern and central North America today, but similar to modern gradients in the Southern Hemisphere mid-latitudes and on the west coast of North America. Latitudinal temperature gradients reconstructed here are broadly representative of Eocene climates, showing that the discrepancy between proxy data and simulations will not be resolved by regional adjustments to paleogeography or reinterpretation of individual fossil assemblages. Similar discrepancies between proxy data and general circulation model simulations for other time periods suggest that there is a basic flaw with the way climate models simulate heat transport to, or loss from, continental surfaces.