External polysaccharides of many pathogenic bacteria form capsules protecting the bacteria from the animal immune system and phage infection. However, some bacteriophages can digest these capsules using glycosidases displayed on the phage particle. We have utilized cryo-electron microscopy to determine the structures of phages K1E and K1-5 and thereby establish the mechanism by which these phages attain and switch their host specificity. Using a specific glycosidase, both phages penetrate the capsule and infect the neuroinvasive human pathogen Escherichia coli K1. In addition to the K1-specific glycosidase, each K1-5 particle carries a second enzyme that allows it to infect E. coli K5, whose capsule is chemically different from that of K1. The enzymes are organized into a multiprotein complex attached via an adapter protein to the virus portal vertex, through which the DNA is ejected during infection. The structure of the complex suggests a mechanism for the apparent processivity of degradation that occurs as the phage drills through the polysaccharide capsule. The enzymes recognize the adapter protein by a conserved N-terminal sequence, providing a mechanism for phages to acquire different enzymes and thus to evolve new host specificities.