R pyocins are ɸCTX-like myophage tailocins of Pseudomonas sp. Adsorption of R pyocins to target strains occurs by the interaction of tail fiber proteins with core lipopolysaccharide (LPS). Here, we demonstrate that N-terminally truncated R pyocin tail fibers corresponding to a region of variation between R-subtypes are sufficient to bind target strains according to R-subtype. We also report the crystal structures of these tail fiber proteins and show that they form an elongated helical trimer composed of three domains arranged linearly from N- to C-terminus: a baseplate proximal head, medial shaft, and distal foot. The head and shaft domains contain novel structural motifs. The foot domain, however, is composed of a conserved jellyroll fold and shares high structural similarity to the tail fiber of myophage AP22, podophage tailspike C-terminal domains (LKA-1 and ɸ297), and several eukaryotic adhesins (discoidin I/II, agglutinin, and octocoral lectin). Many of these proteins bind polysaccharides by means of their distal loop network, a series of highly variable loops at one end of the conserved jellyroll fold backbone. Our structures reveal that the majority of R-subtype specific polymorphisms cluster in patches covering a cleft formed at the oligomeric interface of the head domain and in a large patch covering much of the foot domain, including the distal loop network. Based on the structural variation in distal loops within the foot region, we propose that the foot is the primary sugar-binding domain of R pyocins and R-subtype specific structural differences in the foot domain distal loop network are responsible for binding target strains in an R-subtype dependent manner.