Trade-offs have often been invoked to explain the evolution of ecological specialization. Phytophagous insects have been especially well studied, but there has been little evidence that resource-based trade-offs contribute to the evolution of host specialization in this group. Here, we combine experimental evolution and partial genome resequencing of replicate seed beetle selection lines to test the trade-off hypothesis and measure the repeatability of evolution. Bayesian estimates of selection coefficients suggest that rapid adaptation to a poor host (lentil) was mediated by standing genetic variation at multiple genetic loci and involved many of the same variants in replicate lines. Sublines that were then switched back to the ancestral host (mung bean) showed a more gradual and variable (less repeatable) loss of adaptation to lentil. We were able to obtain estimates of variance effective population sizes from genome-wide differences in allele frequencies within and between lines. These estimates were relatively large, which suggests that the contribution of genetic drift to the loss of adaptation following reversion was small. Instead, we find that some alleles that were favored on lentil were selected against during reversion on mung bean, consistent with the genetic trade-off hypothesis.