Plant and associated insect-damage diversity in the western U.S.A. decreased significantly at the Cretaceous-Paleogene (K-Pg) boundary and remained low until the late Paleocene. However, the Mexican Hat locality (ca. 65 Ma) in southeastern Montana, with a typical, low-diversity flora, uniquely exhibits high damage diversity on nearly all its host plants, when compared to all known local and regional early Paleocene sites. The same plant species show minimal damage elsewhere during the early Paleocene. We asked whether the high insect damage diversity at Mexican Hat was more likely related to the survival of Cretaceous insects from refugia or to an influx of novel Paleocene taxa. We compared damage on 1073 leaf fossils from Mexican Hat to over 9000 terminal Cretaceous leaf fossils from the Hell Creek Formation of nearby southwestern North Dakota and to over 9000 Paleocene leaf fossils from the Fort Union Formation in North Dakota, Montana, and Wyoming. We described the entire insect-feeding ichnofauna at Mexican Hat and focused our analysis on leaf mines because they are typically host-specialized and preserve a number of diagnostic morphological characters. Nine mine damage types attributable to three of the four orders of leaf-mining insects are found at Mexican Hat, six of them so far unique to the site. We found no evidence linking any of the diverse Hell Creek mines with those found at Mexican Hat, nor for the survival of any Cretaceous leaf miners over the K-Pg boundary regionally, even on well-sampled, surviving plant families. Overall, our results strongly relate the high damage diversity on the depauperate Mexican Hat flora to an influx of novel insect herbivores during the early Paleocene, possibly caused by a transient warming event and range expansion, and indicate drastic extinction rather than survivorship of Cretaceous insect taxa from refugia.