Conjugation of the milk protein sodium caseinate and a protein-containing polysaccharide, gum arabic, was achieved through the use of the cross-linking enzyme transglutaminase. The extent of conjugation was monitored by size exclusion separation coupled with a multiangle laser light scattering detector. The elution times of gum arabic solutions incubated with transglutaminase were unchanged over time, whereas incubation of sodium caseinate with transglutaminase resulted in shorter elution times as reaction time increased, indicating the formation of cross-linked caseinate polymers. However, when mixtures of caseinate and gum arabic were incubated with transglutaminase, the elution times were decreased markedly, indicating conjugation between the protein and polysaccharide. The molecular masses of the conjugates increased from approximately 950 to 1600 kDa. This method of protein-polysaccharide conjugation offers noticeable advantages over previously used methods, and the conjugates produced may exhibit unique functional properties.