Here we use multiple genome-wide approaches to map the molecular basis of herbivory from both plant and insect perspectives, focusing on butterflies and their larval host-plants. Parallel genome-wide association studies in the Cabbage White butterfly, Pieris rapae, and its host-plant, Arabidopsis thaliana, pinpointed a small number of butterfly and plant genes that influenced herbivory. These genes, along with much of the genome, were regulated in a dynamic way over the time course of the feeding interaction. Comparative analyses, including diverse butterfly/plant systems, showed a variety of genome-wide responses to herbivory, yet a core set of highly conserved genes in butterflies as well as their host-plants. These results greatly expand our understanding of the genomic causes and evolutionary consequences of ecological interactions across two of Nature's most diverse taxa, butterflies and flowering plants.