Bacteriophages have received recent attention for their therapeutic potential to treat antibiotic-resistant bacterial infections. One particular idea in phage therapy is to use phages that not only directly kill their bacterial hosts but also rely on particular bacterial receptors, such as proteins involved in virulence or antibiotic resistance. In such cases, the evolution of phage resistance would correspond to the loss of those receptors, an approach termed evolutionary steering. We previously found that during experimental evolution, phage U136B can exert selection pressure on Escherichia coli to lose or modify its receptor, the antibiotic efflux protein TolC, often resulting in reduced antibiotic resistance. However, for TolC-reliant phages like U136B to be used therapeutically, we also need to study their own evolutionary potential. Understanding phage evolution is critical for the development of improved phage therapies as well as the tracking of phage populations during infection. Here, we characterized phage U136B evolution in 10 replicate experimental populations. We quantified phage dynamics that resulted in five surviving phage populations at the end of the 10-day experiment. We found that phages from all five surviving populations had evolved higher rates of adsorption on either ancestral or coevolved E. coli hosts. Using whole-genome and whole-population sequencing, we established that these higher rates of adsorption were associated with parallel molecular evolution in phage tail protein genes. These findings will be useful in future studies to predict how key phage genotypes and phenotypes influence phage efficacy and survival despite the evolution of host resistance. Antibiotic resistance is a persistent problem in health care and a factor that may help maintain bacterial diversity in natural environments. Bacteriophages ("phages") are viruses that specifically infect bacteria. We previously discovered and characterized a phage called U136B, which infects bacteria through TolC. TolC is an antibiotic resistance protein that helps bacteria pump antibiotics out of the cell. Over short timescales, phage U136B can be used to evolutionarily "steer" bacterial populations to lose or modify the TolC protein, sometimes reducing antibiotic resistance. In this study, we investigate whether U136B itself evolves to better infect bacterial cells. We discovered that the phage can readily evolve specific mutations that increase its infection rate. This work will be useful for understanding how phages can be used to treat bacterial infections.