Host shifts can lead to ecological speciation and the emergence of new pests and pathogens. However, the mutational events that facilitate the exploitation of novel hosts are poorly understood. Here, we characterize an adaptive walk underpinning the host shift of the aphid Myzus persicae to tobacco, including evolution of mechanisms that overcame tobacco chemical defenses. A series of mutational events added as many as 1.5 million nucleotides to the genome of the tobacco-adapted subspecies, M. p. nicotianae, and yielded profound increases in expression of an enzyme that efficiently detoxifies nicotine, both in aphid gut tissue and in the bacteriocytes housing the obligate aphid symbiont Buchnera aphidicola. This dual evolutionary solution overcame the challenge of preserving fitness of a mutualistic symbiosis during adaptation to a toxic novel host. Our results reveal the intricate processes by which genetic novelty can arise and drive the evolution of key innovations required for ecological adaptation.