Evolutionary innovations are often achieved by repurposing existing genes to perform new functions; however, the mechanisms enabling the transition from old to new remain controversial. We identified mutations in bacteriophage λ’s host-recognition gene J that confer enhanced adsorption to λ’s native receptor, LamB, and the ability to access a new receptor, OmpF. The mutations destabilize particles and cause conformational bistability of J, which yields progeny of multiple phenotypic forms, each proficient at different receptors. This work provides an example of how nongenetic protein variation can catalyze an evolutionary innovation. We propose that cases where a single genotype can manifest as multiple phenotypes may be more common than previously expected and offer a general mechanism for evolutionary innovation.