The emergence of antibiotic resistance has sparked interest in phage therapy, which uses virulent phages as antibacterial agents. Bacteriophage PP01 has been studied for potential bio-control of Escherichia coli O157:H7, its natural host, but in the laboratory, PP01 can be inefficient at killing this bacterium. Thus, the goal of this study was to improve the therapeutic potential of PP01 through short-term experimental evolution. Four replicate populations of PP01 were serially passaged 21 times on non-evolving E. coli O157:H7 with the prediction that the evolved phage populations would adsorb faster and more efficiently kill the host bacteria. Dead-cell adsorption assays and in vitro killing assays confirmed that evolved viruses improved their adsorption ability on E. coli O157:H7, and adapted to kill host bacteria faster than the wildtype ancestor. Sequencing of candidate tail-fiber genes revealed that the phage populations evolved in parallel; the lineages shared two point mutations in gp38 that encodes a host recognition protein, and surprisingly shared a ~600 bp deletion in gp37 that encodes the distal tail fibers. In contrast, no mutations were observed in the gp12 gene encoding PP01’s short tail fibers. We discuss the functional role of the observed mutations, including the possible adaptive role of the evolved deletions. This study demonstrates how experimental evolution can be used to select for viral traits that improve phage attack of an important bacterial pathogen, and that the molecular targets of selection include loci contributing to cell attachment and phage virulence.