The convergence of phage-displayed peptide libraries and recombinant viral vectors launched a promising new direction in targeted viral gene therapeutics, but the translation of targeting peptides to functional cancer therapeutic agents has been challenging. Here, we report progress in developing a successful strategy to optimize targeted viral infection through adenovirus-displayed, semirandom peptide libraries. A phage-derived peptide targeting the prostate-specific membrane antigen (PSMA) was genetically incorporated into the adenoviral capsid Fiber protein and flanked by random peptide cassettes. The resulting adenovirus library was biopanned against PSMA-expressing cells and tumors to identify a PSMA-retargeted adenovirus. While the initial peptide alone could not target viral infection, the selected virus preferentially infects PSMA-expressing cells through the targeting peptide and infects LNCaP tumors after intravenous injection. Our results indicate that virus-displayed, semirandom peptide libraries can be used to optimize targeting infection. This approach represents a novel principle for developing targeted agents in a variety of disease models.