Paleoecological studies enhance our understanding of biotic response to climate change because they consider timescales not accessible through laboratory or ecological studies. From 60 to 51 million years ago (Ma), global temperatures gradually warmed to the greatest sustained highs of the last 65 million years. Superimposed on this gradual warming is a transient spike of high temperature and pCO 2 (partial pressure of carbon dioxide in the atmosphere; the Paleocene-Eocene Thermal Maximum 55.8 Ma) and a subsequent short-term cooling event (∼54 Ma). The highly resolved continental fossil record of the Bighorn Basin, Wyoming, USA, spans this interval and is therefore uniquely suited to examine the long-term effects of temperature change on the two dominant groups in terrestrial ecosystems, plants and insect herbivores. We sampled insect damage on fossil angiosperm leaves at nine well-dated localities that range in age from 52.7 to 59 Ma. A total of 9071 leaves belonging to 107 species were examined for the presence or absence of 71 insect-feeding damage types. Damage richness, frequency, and composition were analyzed on the bulk floras and individual host species. Overall, there was a strong positive correlation between changes in damage richness and changes in estimated temperature, a weak positive relationship for damage frequency and temperature, and no significant correlation for floral diversity. Thus, insect damage richness appears to be more sensitive to past climate change than to plant diversity, although plant diversity in our samples only ranges from 6 to 25 dicot species. The close tracking of the richness of herbivore damage, a presumed proxy for actual insect herbivore richness, to both warming and cooling over a finely divided, extended time interval has profound importance for interpreting the evolution of insects and plant–insect associations in the context of deep time. Our results also indicate that increased insect herbivory is likely to be a net long-term effect of anthropogenic warming.