Leaf mining is one of the major feeding strategies of herbivorous insects. The leaf-mining insects inhabit, consume, and develop within the leaf tissues. Their mines provide much of their life history, including the developmental processes (e.g., feeding, defecation, pupation) and outcomes (e.g., larval death, parasitism, or adult emergence). Mined leaves can be found in the fossil records from the Middle Triassic to the Recent. As leaf-mining insects are rarely preserved as body fossils, the leaf mine fossils offer unique insights into the evolutionary trajectories of such plant-insect interactions. However, these interactions have yet to be underexplored in Japanese plant fossils, with only two leaf mine fossils recorded from Japan to date. This study investigates leaf mines on Cenozoic plant fossils from Japan, comparing their morphological features with previous examples in reference to the Damage Types (DT) by Labandeira and his colleagues. The taxonomic affiliations of the miners were inferred based on the mine’s morphological traits. We examined ca. 2,500 fossil specimens from various deposits dating to the Paleocene and Pliocene. As a result, potential leaf mines were discovered from 69 fossil leaves, representing at least 19 distinct DTs, including two potentially new DTs. Based on diagnostic features, some mines were attributed to Lepidoptera, such as Stigmella (Nepticulidae) and Opostegidae. Each type of leaf mine was found specifically on certain plant taxa, suggesting high host specificity. Notably, the diversity of leaf mines in the Paleocene Minato Formation was more significant than in some contemporaneous deposits from Europe and North America. This may reflect the richness of herbivorous insects during the Paleocene and differences in preservation potential. Our discovery of abundant and diverse leaf mine fossils from Japan will provide a foundation for future research directions, such as elucidating the evolutionary history of specific insect lineages and investigating the dynamics in interactions across spatiotemporal scales.