The R-type pyocins are high-molecular weight bacteriocins produced by some strains of Pseudomonas aeruginosa to specifically kill other strains of the same species. Structurally, the R-type pyocins are similar to “simple” contractile tails, such as those of phage P2 and Mu. The pyocin recognizes and binds to its target with the help of fibers that emanate from the baseplate structure at one end of the particle. Subsequently, the pyocin contracts its sheath and drives the rigid tube through the host cell envelope. This causes depolarization of the cytoplasmic membrane and cell death. The host cell surface-binding fiber is ~340 Å-long and is attached to the baseplate with its N-terminal domain. Here, we report the crystal structures of C-terminal fragments of the R1 and R2 pyocin fibers that comprise the distal, receptor-binding part of the protein. Both proteins are ~240 Å-long homotrimers in which slender rod-like domains are interspersed with more globular domains—two tandem knob domains in the N-terminal part of the fragment and a lectin-like domain at its C-terminus. The putative substrate binding sites are separated by about 100 Å, suggesting that binding of the fiber to the cell surface causes the fiber to adopt a certain orientation relative to the baseplate and this then triggers sheath contraction.