There is a dogma within whey protein modification, which dictates the necessity of pretreatment to enzymatic cross-linking of β-lactoglobulin (β-Lg). Here microbial transglutaminase (MTG) cross-linked whey proteins and β-Lg effectively in 50 mM NaHCO₃, pH 8.5, without pretreatment. Cross-linked β-Lg spanned 18 to >240 kDa, where 6 of 9 glutamines reacted with 8 of 15 lysines. The initial isopeptide bond formation caused loss of β-Lg native structure with t_1/2 = 3 h, while the polymerization occurred with t_1/2 = 10 h. Further, cross-linking effects on protein carbohydrate interaction have been overlooked, leaving a gap in understanding of these complex food matrices. Complexation with alginate showed that β-Lg cross-linking decreased onset of particle formation, hydrodynamic diameter, stoichiometry (β-Lg/alginate) and dissociation constant. The complexation was favored at higher temperatures (40 °C), suggesting that hydrophobic interactions were important. Thus, β-Lg was cross-linked without pretreatment and the resulting polymers gave rise to altered complexation with alginate.