One-quarter of extant Eukaryotic species are herbivorous insects, yet the genomic basis of this extraordinary adaptive radiation is unclear. Recently-derived herbivorous species hold promise for understanding how colonization of living plant tissues shaped the evolution of herbivore genomes. Here, we characterized exceptional patterns of evolution coupled with a recent (400 million years ago (mya) spurred the diversification of plant-feeding (herbivorous) insects and triggered an ongoing chemical co-evolutionary arms race. Because ancestors of most herbivorous insects first colonized plants >200 mya, the sands of time have buried evidence of how their genomes changed with their diet. We leveraged the serendipitous intersection of two genetic model systems: a close relative of yeast-feeding fruit fly (Drosophila melanogaster), the \"wasabi fly\" (Scaptomyza flava), that evolved to consume mustard plants including Arabidopsis thaliana. The yeast-to-mustard dietary transition remodeled the flys gene repertoire for sensing and detoxifying chemicals. Although many genes were lost, some underwent duplications that encode the most efficient detoxifying enzymes against mustard oils known from animals.