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. In this study, a proteomic analysis of the novel temperate Klebsiella bacteriophage, NAR688, revealed that the bacteriophage encodes a pore-forming bacteriocin (toxin) we call telocin A. Purified telocin A was shown to have bactericidal activity against a large number of Klebsiella strains. The outer membrane porin, OmpK36, was shown to be essential for telocin A sensitivity in target cells. Specific epitopes of the OmpK36 protein were found to be involved in telocin A reception by subjecting a set of engineered loop-chimeric OmpK36 variants to the bacteriocin. We further identified the cognate telocin A immunity protein and found it to be localised to the inner membrane of Klebsiella cells through sucrose gradient fractionation of purified cell membranes. To investigate the broader relevance of this bacteriocin-bacteriophage relationship in Klebsiella, the genomic contexts of other bacteriocins of Klebsiella were analysed, revealing that bacteriocin-bacteriophage associations are common in the genus. In future work, the potential evolutionary benefits conferred to host cells by NAR688 lysogeny will be examined through fitness and competition experiments. Additionally, three novel bacteriocins identified in the genomes of other, related temperate bacteriophages will be purified and assessed alone and in combination with telocin A for their ability to kill different strains of Klebsiella. The findings will provide insights into the abundance and classification of bacteriophage-encoded bacteriocins, and their potential applications in the treatment of Klebsiella infections.