The processes responsible for the evolution of key innovations, whereby lineages acquire qualitatively new functions that expand their ecological opportunities, remain poorly understood. We examined how a virus, bacteriophage λ, evolved to infect its host, Escherichia coli, through a novel pathway. Natural selection promoted the fixation of mutations in the virus's host-recognition protein, J, that improved fitness on the original receptor, LamB, and set the stage for other mutations that allowed infection through a new receptor, OmpF. These viral mutations arose after the host evolved reduced expression of LamB, whereas certain other host mutations prevented the phage from evolving the new function. This study shows the complex interplay between genomic processes and ecological conditions that favor the emergence of evolutionary innovations.