Complex glycans cover the gut epithelial surface to protect the cell from the environment. Invasive pathogens must breach the glycan layer before initiating infection. While glycan degradation is crucial for infection, this process is inadequately understood. Salmonella contains 47 glycosyl hydrolases (GHs) that may degrade the glycan. We hypothesized that keystone genes from the entire GH complement of Salmonella are required to degrade glycans to change infection. This study determined that GHs recognize the terminal monosaccharides (N-acetylneuraminic acid (Neu5Ac), galactose, mannose, and fucose) and significantly (p < 0.05) alter infection. During infection, Salmonella used its two GHs sialidase nanH and amylase malS for internalization by targeting different glycan structures. The host glycans were altered during Salmonella association via the induction of N-glycan biosynthesis pathways leading to modification of host glycans by increasing fucosylation and mannose content, while decreasing sialylation. Gene expression analysis indicated that the host cell responded by regulating more than 50 genes resulting in remodeled glycans in response to Salmonella treatment. This study established the glycan structures on colonic epithelial cells, determined that Salmonella required two keystone GHs for internalization, and left remodeled host glycans as a result of infection. These data indicate that microbial GHs are undiscovered virulence factors.