Despite a very large number of bacterial exopolysaccharides have been reported, detailed knowledge on their molecular structures and associative interactions with proteins is lacking. Small-angle X-ray scattering, dynamic light scattering and analytical ultracentrifugation (AUC) were used to characterize the interactions of six lactic acid bacterial heteroexopolysaccharides (HePS-1-HePS-6) with β-lactoglobulin (BLG). Compared to free HePSs, a large increase in the X-ray radius of gyration RG, maximum length L and hydrodynamic diameter dH of HePS-1-HePS-4 mixed with BLG revealed strong aggregation, the extent of which depended on the compact conformation and degree of branching of these HePSs. No significant effects were observed with HePS-5 and HePS-6. Turbidity and AUC analyses showed that both soluble and insoluble BLG-HePS complexes were formed. The findings provide new insights into the role of molecular structures in associative interactions between HePSs and BLG which has relevance for various industrial applications.