Due to the prevalence of encapsulated bacteria, the capsule is the first barrier encountered by many phages. This layer, usually made of polysaccharides, can block the access of phages to their cell wall receptors. To overcome this, some phages have specific depolymerase enzymes (Dpos) in their receptor-binding proteins. Here, we have quantified the predictability of phage-bacteria interactions based on the capsular locus type of the host (CLT) and Dpos. For this, we have used Klebsiella pneumoniae (Kpn) as a model, because of its high capsular diversity and its importance in global health. We have analysed the complete interaction network of a Kpn-phage collection, comprising 138 Kpn isolates and 46 diverse phages. Spot tests revealed that the majority of phages showed capsular specificity, with their pattern of infection being accurately predicted (92%) by the CLT of the host. Consequently, phage-encoded Dpos, which have often undergone horizontal gene transfer across large taxonomic scales, were key determinants of host tropism. The identity tolerance of phage Dpos was high, as shown by the predicted capsular tropism of RefSeq prophages for 13 important CLTs. Even though capsules and Dpos predicted the first steps of virion recognition and adsorption, their accuracy dropped for productive infections (53%). Additionally, we have found four phages with a broader host range that showed both capsule-dependent and independent tropism. This was also evidenced by their ability to infect acapsular bacteria depending on the genetic background of the host. These findings expand our knowledge of the complex interactions between bacteria and their viruses and point out the feasibility of predicting the first steps of phage infection using the genome sequences of phages and hosts.