Klebsiella pneumoniae has risen to prominence as a major threat to human health, with hypervirulent and drug-resistant lineages spreading globally. Given their antimicrobial resistant phenotypes, new therapies are required for the treatment of these infections, and bacteriophages (phages) that kill Klebsiella are being identified for use in phage therapy. In order to circumvent the evolution of phage-resistance taking hold the way that drug-resistance has, clear and considered actions are needed in selecting the phages that would be used in therapeutic cocktails. It is known that annotation of phage genomes is poor, potentially obscuring those phages with the most therapeutic potential. Here we show that phages isolated from infrequently sampled environments have features of therapeutic potential and developed a computational tool called STEP3 to understand the evolutionary features that distinguish the component parts of diverse phages, features that proved particularly suitable to detection of virion proteins with only distantly related homologies. These features were integrated into an ensemble framework to achieve a stable and robust prediction performance by STEP3. Proteomics-based analysis of two phages validated the prediction accuracy of STEP3 and revealed the virions contain component parts that include DNA-binding factors, otherwise unrecognizable capsule degradation enzymes and membrane translocation factors.