Bacteriophages recognize their host cells with the help of tail fiber and tailspike proteins that bind, cleave, or modify certain structures on the cell surface. The spectrum of ligands to which the tail fibers and tailspikes can bind is the primary determinant of the host range. Bacteriophages with multiple tailspike/tail fibers are thought to have a wider host range than their less endowed relatives but the function of these proteins remains poorly understood. Here, we describe the structure, function, and substrate specificity of three tailspike proteins of bacteriophage CBA120—TSP2, TSP3 and TSP4 (orf211 through orf213, respectively). We show that tailspikes TSP2, TSP3 and TSP4 are hydrolases that digest the O157, O77, and O78 Escherichia coli O-antigens, respectively. We demonstrate that recognition of the E. coli O157:H7 host by CBA120 involves binding to and digesting the O157 O-antigen by TSP2. We report the crystal structure of TSP2 in complex with a repeating unit of the O157 O-antigen. We demonstrate that according to the specificity of its tailspikes TSP2, TSP3, and TSP4, CBA120 can infect E. coli O157, O77, and O78, respectively. We also show that CBA120 infects Salmonella enterica serovar Minnesota, and this host range expansion is likely due to the function of TSP1. Finally, we describe the assembly pathway and the architecture of the TSP1–TSP2–TSP3–TSP4 branched complex in CBA120 and its related ViI-like phages.