The Late Triassic saw a flourish of plant–arthropod interactions. By the Late Triassic, insects had developed all distinct strategies of herbivory, notably including some of the earliest occurrences of leaf-mining. Herein we describe exceptionally well-preserved leaf-mine trace fossils on a Cladophlebis Brongniart fern pinnule from the Momonoki Formation, Mine Group, Japan (Middle Carnian), representing the oldest unequivocal leaf-mines from East Asia. The mines all display a distinctive frass trail—a continuous meandering line, which later becomes a broad band containing spheroidal particles—demonstrating larval development. Although the shapes of the frass trails are generally comparable to those of Lepidoptera or Coleoptera, they cannot be unequivocally assigned to a specific extant leaf-mining taxon. Furthermore, elemental analyses by X-ray fluorescence (XRF) reveals that the frass trail comprises phosphate coprolites. The quantitative variations in P, S, and Si between coprolites and leaf veins may reflect physiological processes (e.g., consumption, absorption, and excretion) mediated by plant chemicals. Our findings reinforce the idea that leaf-mining had become a pervasive feeding strategy of herbivorous insects by the Late Triassic.