Herbivorous insects are extraordinarily diverse, yet are found in only one-third of insect orders. This skew may result from barriers to plant colonization, coupled with phylogenetic constraint on plant-colonizing adaptations. Physical barriers have been surmounted through the evolution of key morphological innovations, such as the plant-penetrating ovipositor. Despite their significance, the evolution and genetic basis of such innovations have not been well studied. Ovipositors densely lined with hard bristles have evolved repeatedly in herbivorous lineages within the Drosophilidae. Here, we focus on the evolution of this trait in Scaptomyza, an herbivorous radiation nested in a microbe-feeding clade, sister to Hawaiian Drosophila. Our phylogenetic approach revealed that ovipositor bristle number increased as herbivory evolved. We then dissected the genomic architecture of variation in ovipositor bristle number within S. flava through a genome-wide association study. Top associated variants were enriched for transcriptional repressors, and the strongest associations included genes contributing to peripheral nervous system development. Genotyping individual flies replicated the association at a variant upstream of Gαi, a neural development gene, contributing to a gain of 0.58 bristles/major allele. These results show that a key morphological adaptation required for plant colonization may have arisen through regulatory changes involving conserved developmental genes.