Bacteriophages are the most numerous organisms in the biosphere. In spite of their biological significance and the spectrum of potential applications, little high-resolution structural detail is available on their receptor-binding fibers. Here we present the crystal structure of the receptor-binding tip of the bacteriophage T4 long tail fiber, which is highly homologous to the tip of the bacteriophage lambda side tail fibers. This structure reveals an unusual elongated six-stranded antiparallel beta-strand needle domain containing seven iron ions coordinated by histidine residues arranged colinearly along the core of the biological unit. At the end of the tip, the three chains intertwine forming a broader head domain, which contains the putative receptor interaction site. The structure reveals a previously unknown beta-structured fibrous fold, provides insights into the remarkable stability of the fiber, and suggests a framework for mutations to expand or modulate receptor-binding specificity.