Klebsiella pneumoniae carries a thick polysaccharide capsule. This highly variable chemical structure plays an important role in its virulence. Many Klebsiella bacteriophages recognize this capsule with a receptor binding protein (RBP) that contains a depolymerase domain. This domain degrades the capsule to initiate phage infection. RBPs are highly specific and thus largely determine the host spectrum of the phage. A majority of known Klebsiella phages have only one or two RBPs, but phages with up to 11 RBPs with depolymerase activity and a broad host spectrum have been identified. A detailed bioinformatic analysis shows that similar RBP domains repeatedly occur in K. pneumoniae phages with structural RBP domains for attachment of an RBP to the phage tail (anchor domain) or for branching of RBPs (T4gp10-like domain). Structural domains determining the RBP architecture are located at the N-terminus, while the depolymerase is located in the center of protein. Occasionally, the RBP is complemented with an autocleavable chaperone domain at the distal end serving for folding and multimerization. The enzymatic domain is subjected to an intense horizontal transfer to rapidly shift the phage host spectrum without affecting the RBP architecture. These analyses allowed to model a set of conserved RBP architectures, indicating evolutionary linkages.