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 (protein toxin) we call Telocin A (TelA). Purified TelA was shown to have antibacterial activity against many Klebsiella strains. A cognate TelA immunity protein, ImmA, was identified from the NAR688 genome and shown to confer resistance to TelA killing. Additionally, the outer membrane porin, OmpK36, was shown to be essential for TelA sensitivity in target cells. To assess whether related Klebsiella bacteriophages also encode bacteriocins, the genomes of NAR688-related bacteriophages were interrogated. Four temperate bacteriophages encoding four distinct bacteriocin-immunity protein pairs were identified. These bacteriocins were purified and shown to have antibacterial activity against a broad range of Klebsiella strains. These findings raise questions about ecological and evolutionary relationships between bacteria, bacteriophages and bacteriocins, and further, highlight the potential for bacteriocins to be applied in the control of Klebsiella populations.