Rapid adaptation can be necessary to prevent extinction when populations are exposed to extremely marginal or stressful environments. Factors that affect the likelihood of evolutionary rescue from extinction have been identified, but much less is known about the evolutionary dynamics and genomic basis of successful evolutionary rescue, particularly in multicellular organisms. We conducted an evolve-and-resequence experiment to investigate the dynamics of evolutionary rescue at the genetic level in the cowpea seed beetle, Callosobruchus maculatus, when it is experimentally shifted to a stressful host plant, lentil (Lens culinaris). Low survival (~1%) at the onset of the experiment caused population decline. But adaptive evolution quickly rescued the population with survival rates climbing to 69\% by the F5 generation and 90\% by the F10 generation. Population genomic data showed that rescue likely was caused by rapid evolutionary change at multiple loci, with many alleles fixing or nearly fixing within five generations of selection on lentil. By comparing estimates of selection across five lentil-adapted C. maculatus populations (two new sublines and three long-established lines), we found that adaptation to lentil can involve a mixture of repeated and idiosyncratic evolutionary changes. Parallel evolutionary changes were particularly pronounced in sublines formed after the parent line had passed through an initial bottleneck. Overall, our results suggest that evolutionary rescue in this system can be driven by very strong selection on a modest number of loci, and these results provide empirical evidence that ecological dynamics during evolutionary rescue can cause distinct evolutionary trajectories and genomic signatures.