Herbivorous insects account for more than one-quarter of species diversity in modern fauna. Reciprocal interactions between plants and herbivorous insects have long been investigated from both sides over various timescales; however, it is still shrouded in mystery when it comes to its origin and initial evolution. As the basal lineage of land plants, bryophytes may offer the key to infer the initial evolution of plant–herbivore interactions. Associations between bryophytes and animals have largely been overlooked, probably because bryophytes lack flowers and seeds, by which plants intensely make mutualistic relationships with animals. In fact, bryophytes are apparently less susceptible to herbivore, and yet we found that some group of insects is specialized to feed on a subset of bryophyte species. We show our phylogeny-based studies on two insect lineages, Micropterigidae (Lepidoptera) and Rhagionidae (Diptera), which exemplify the long-standing associations between herbivorous insects and bryophytes. We illustrate how the bryophyte-feeding insects have diverged in Japan and thereby discuss mechanisms underlying the common patterns of diversification of bryophyte-feeding insects.