Cholera toxin (CT) enters and intoxicates host cells after binding cell surface receptors using its B subunit (CTB). The ganglioside (glycolipid) GM1 is thought to be the sole CT receptor; however, the mechanism by which CTB binding to GM1 mediates internalization of CT remains enigmatic. Here we report that CTB binds cell surface glycoproteins. Relative contributions of gangliosides and glycoproteins to CTB binding depend on cell type, and CTB binds primarily to glycoproteins in colonic epithelial cell lines. Using a metabolically incorporated photocrosslinking sugar, we identified one CTB-binding glycoprotein and demonstrated that the glycan portion of the molecule, not the protein, provides the CTB interaction motif. We further show that fucosylated structures promote CTB entry into a colonic epithelial cell line and subsequent host cell intoxication. CTB-binding fucosylated glycoproteins are present in normal human intestinal epithelia and could play a role in cholera.