Polyphenols derived from tea are thought to be important for human health. We show using a combination of particle tracking microrheology and small-angle neutron scattering that polyphenols acts as cross-linkers for purified gastrointestinal mucin, derived from the stomach and the duodenum. Both naturally derived purified polyphenols, and green and black tea extracts are shown to act as cross-linkers. The main active cross-linking component is found to be the galloylated forms of catechins. The viscosity, elasticity and relaxation time of the mucin solutions experience an order of magnitude change in value upon addition of the polyphenol cross-linkers. Similarly small-angle neutron scattering experiments demonstrate a sol-gel transition with the addition of polyphenols, with a large increase in the scattering at low angles, which is attributed to the formation of large scale (>10 nm) heterogeneities during gelation. Cross-linking of mucins by polyphenols is thus expected to have an impact on the physicochemical environment of both the stomach and duodenum; polyphenols are expected to modulate the barrier properties of mucus, nutrient absorption through mucus and the viscoelastic microenvironments of intestinal bacteria.