Tailed bacteriophages (phages) are one of the most abundant life forms on Earth. They encode highly efficient molecular machines to infect bacteria, but the initial interactions between a phage and a bacterium that then lead to irreversible virus attachment and infection are poorly understood. This information is critically needed to engineer machines with novel host specificities in order to combat antibiotic resistance, a major threat to global health today. The tailed phage T4 encodes a specialized device for this purpose, the long tail fiber (LTF), which allows the virus to move on the bacterial surface and find a suitable site for infection. Consequently, the infection efficiency of phage T4 is one of the highest, reaching the theoretical value of 1. Although the atomic structure of the tip of the LTF has been determined, its functional architecture and how interactions with two structurally very different Escherichia coli receptor molecules, lipopolysaccharide (LPS) and outer membrane protein C (OmpC), contribute to virus movement remained unknown. Here, by developing direct receptor binding assays, extensive mutational and biochemical analyses, and structural modeling, we discovered that the ball-shaped tip of the LTF, a trimer of gene product 37, consists of three sets of symmetrically alternating binding sites for LPS and/or OmpC. Our studies implicate reversible and dynamic interactions between these sites and the receptors. We speculate that the LTF might function as a "molecular pivot" allowing the virus to "walk" on the bacterium by adjusting the angle or position of interaction of the six LTFs attached to the six-fold symmetric baseplate.