Bacteriophages, the viruses of bacteria, are proposed to drive bacterial population dynamics, yet direct evidence of their impact on natural populations is limited. Here we identified viral sequences in a metapopulation of wild plant-associated Pseudomonas spp. genomes. We discovered that the most abundant viral cluster does not encode an intact phage but instead encodes a tailocin - a phage-derived element that bacteria use to kill competitors for interbacterial warfare. Each pathogenic Pseudomonas sp. strain carries one of a few distinct tailocin variants, which target variable polysaccharides in the outer membrane of co-occurring pathogenic strains. Analysis of historic herbarium samples from the last 170 years revealed that the same tailocin and receptor variants have persisted in the Pseudomonas populations for at least two centuries, suggesting the continued use of a defined set of tailocin haplotypes and receptors. These results indicate that tailocin genetic diversity can be mined to develop targeted "tailocin cocktails" for microbial control.