The study of bacteriophage-host interactions has yielded insights into the basic biology of many bacterial pathogens; however, our understanding of these relationships in Klebsiella spp. is limited. Recently, bioinformatic analyses have identified associations between a number of temperate bacteriophages and proteinaceous bactericidal toxins, bacteriocins, in multiple bacterial genera. Despite the potential for both bacteriophages and bacteriocins to serve as modulators of microbial communities, only one bacteriophage-encoded bacteriocin has been studied experimentally previously. In this study, a proteomic analysis of the novel temperate Klebsiella phage, NAR688, revealed that the phage encodes a pore-forming bacteriocin, telocin A. Purified telocin A was shown to have potent bactericidal activity against 29 strains of Klebsiella. Proteins involved in telocin A reception in target cells and immunity in producing cells were identified, and the transfer of the toxigenic phenotype to new Klebsiella strains through NAR688 lysogeny was demonstrated. To investigate the broader relevance of this bacteriocin-bacteriophage relationship in Klebsiella, the genomic contexts of other bacteriocins of Klebsiella (klebicins) were analysed, revealing that bacteriocin-bacteriophage associations are common in the genus, and that bacteriocins can undergo recombination between phage genomes. In future work, the ecological significance of the tripartite bacteriocin-bacteriophage-bacterium relationship will be examined through fitness and competition experiments comparing Klebsiella strains harbouring NAR688 to strains with various levels of susceptibility to the phage and its bacteriocin. Additionally, three novel bacteriocins identified in the genomes of three variants of NAR688 will be purified and assessed alone and in combination with telocin A for their ability to kill various strains of Klebsiella. The findings, together with further investigations into the diversity of other phage-encoded bacteriocins, will provide insights into the potential for the phage-bacteriocin relationship to accelerate bacteriocin diversification, thereby influencing the ongoing warfare between bacterial competitors.