Alginate and whey protein are common additives in food production improving storage stability, texture and nutritional value. Alginate forms complexes with whey protein and inhibits proteolysis by pepsin and trypsin, but the influence of alginate protein complexation on digestion is poorly understood. This study shows that whey protein cross-linking by microbial transglutaminase dramatically decreased particle size (2-fold) and viscosity of alginate protein complexes. The INFOGEST in vitro simulated gastrointestinal digestion of whey protein was increased by cross-linking (16%) and suppressed by alginate, most pronounced with high mannuronic acid and least with high guluronic acid content. Sizes of alginate whey protein particles increased during gastric digestion, whereas for cross-linked whey protein complexes the size initially increased, but returned to their initial size at the end of gastric digestion. While alginate is not degraded by human enzymes, a few gut bacteria were recently found to encode lyases and other enzymes metabolizing alginate. Alginate lyase added to the intestinal phase enhanced digestion (9%) as controlled by alginate composition and enzyme specificity. Thus we provide evidence that use of hydrocolloids and processing of protein strongly influence digestion and should be considered when using food additives.