The intracellular pathogen Listeria monocytogenes is distinguished by its ability to invade and replicate within mammalian cells. Remarkably, of the 15 serovars within the genus, strains belonging to serovar 4b cause the majority of listeriosis clinical cases and outbreaks. The Listeria O-antigens are defined by subtle structural differences amongst the peptidoglycan-associated wall-teichoic acids (WTAs), and their specific glycosylation patterns. Here, we outline the genetic determinants required for WTA decoration in serovar 4b L. monocytogenes, and demonstrate the exact nature of the 4b-specific antigen. We show that challenge by bacteriophages selects for surviving clones that feature mutations in genes involved in teichoic acid glycosylation, leading to a loss of galactose from both wall teichoic acid and lipoteichoic acid molecules, and a switch from serovar 4b to 4d. Surprisingly, loss of this galactose decoration not only prevents phage adsorption, but leads to a complete loss of surface-associated Internalin B (InlB),the inability to form actin tails, and a virulence attenuation in vivo. We show that InlB specifically recognizes and attaches to galactosylated teichoic acid polymers, and is secreted upon loss of this modification, leading to a drastically reduced cellular invasiveness. Consequently, these phage-insensitive bacteria are unable to interact with cMet and gC1q-R host cell receptors, which normally trigger cellular uptake upon interaction with InlB. Collectively, we provide detailed mechanistic insight into the dual role of a surface antigen crucial for both phage adsorption and cellular invasiveness, demonstrating a trade-off between phage resistance and virulence in this opportunistic pathogen.