Sequencing of bacterial genomes has revealed an abundance of prophage sequences in many bacterial species. Since these sequences are accessible, through recombination, to infecting phages, bacteria carry an arsenal of genetic material that can be used by these viruses. We develop a mathematical model to isolate the effects of this phenomenon on the coevolution of temperate phage and bacteria. The model predicts that prophage sequences may play a key role in maintaining the phage population in situations that would otherwise favour host cell resistance. In addition, prophage recombination facilitates the existence of multiple phage types, thus promoting diverse co-existence in the phage-host ecosystem. Finally, because the host carries an archive of previous phage strategies, prophage recombination can drive waves of innovation in the host cell population.