Bacteriocins are antimicrobial proteins produced by bacteria to assist in outcompeting closely-related species for resources, nutrients and space. Due to their potent antibacterial properties, bacteriocins are becoming increasingly valuable in food and health industries. Traditional large-scale phenotypic screening methods to hunt bacteriocins are often time-consuming and costly. Therefore, we present a genomics-based methodology to identify highly divergent and uncharacterized bacteriocins in Klebsiella genomes. Using the BAGEL4 database and additional literature, we curated a database of bacteriocin sequence representatives, and then used HHblits to construct HMM profiles to screen 452 K. pneumoniae genomes collected from patients in Alfred Hospital. Next we investigated the bacteriocin distribution across this diverse population, made up of genetically-distinct lineages. We identified at least 3 bacteriocin types across the dataset, after confirming their putative intactness via analysis of the surrounding expected bacteriocin-associated content such as export and immunity genes. Colicin V-like bacteriocins were very common, present in 83% of Klebsiella genomes. Moreover, they displayed both sequence and putative protein structural variation across 42 alleles which was lineage-specific. Structural alignments identified mutational hot spots, offering insights into their potential variable antimicrobial spectra. We aim to predict bacteriocin immunity profiles for each isolate using the identified putative immunity proteins along with their putative receptor binding proteins. This in silico approach provides a rapid, targeted pathway to identify alternative antimicrobials, reducing the time and cost associated with large-scale phenotypic screening.