Interactions of exopolysaccharides and proteins are of great importance in food science, but complicated to analyze and quantify at the molecular level. A surface plasmon resonance procedure was established to characterize binding of seven structure-determined, branched hetero-exopolysaccharides (HePSs) of 0.14–4.9 MDa from lactic acid bacteria to different milk proteins (β-casein, κ-casein, native and heat-treated β-lactoglobulin) at pH 4.0–5.0. Maximum binding capacity (RUmax) and apparent affinity (KA,app) were HePS- and protein-dependent and varied for example 10- and 600-fold, respectively, in the complexation with native β-lactoglobulin at pH 4.0. Highest RUmax and KA,app were obtained with heat-treated β-lactoglobulin and β-casein, respectively. Overall, RUmax and KA,app decreased 6- and 20-fold, respectively, with increasing pH from 4.0 to 5.0. KA,app was influenced by ionic strength and temperature, indicating that polar interactions stabilize HePS–protein complexes. HePS size as well as oligosaccharide repeat structure, conferring chain flexibility and hydrogen bonding potential, influence the KA,app.