Bacteriophage T4 initially recognizes its host cells using its long tail fibers. Long tail fibers consist of a phage-proximal and a phage-distal rod, each around 80 nm long and attached to each other at a slight angle. The phage-proximal rod is formed by a homo-trimer of gene product 34 (gp34) and is attached to the phage-distal rod by a monomer of gp35. The phage-distal rod consists of two protein trimers: a trimer of gp36, attached to gp35, although most of the phage-distal rod, including the receptor-binding domain, is formed by a trimer of gp37. In this review, we discuss what is known about the detailed structure and function of the different long tail fiber domains. Partial crystal structures of gp34 and gp37 have revealed the presence of new protein folds, some of which are present in several repeats, while others are apparently unique. Gp38, a phage chaperone protein necessary for folding of gp37, is thought to act on an α-helical coiled-coil region in gp37. Future studies should reveal the remaining structure of the long tail fibers, how they assemble into a functional unit, and how the long tail fibers trigger the infection process after successful recognition of a suitable host bacterium.