Bacteriophages recognize and bind to their hosts with the help of receptor-binding proteins (RBPs) that emanate from the phage particle in the form of fibers or tailspikes. RBPs show a great variability in their shapes, sizes, and location on the particle. Some RBPs are known to depolymerize surface polysaccharides of the host while others show no enzymatic activity. Here we report that both RBPs of podovirus G7C - tailspikes gp63.1 and gp66 - are essential for infection of its natural host bacterium E. coli 4s that populates the equine intestinal tract. We characterize the structure and function of gp63.1 and show that unlike any previously described RPB, gp63.1 deacetylates surface polysaccharides of E. coli 4s leaving the backbone of the polysaccharide intact. We demonstrate that gp63.1 and gp66 form a stable complex, in which the N-terminal part of gp66 serves as an attachment site for gp63.1 and anchors the gp63.1-gp66 complex to the G7C tail. The esterase domain of gp63.1 as well as domains mediating the gp63.1-gp66 interaction is widespread among all three families of tailed bacteriophages.