Lactic acid bacteria exopolysaccharides (EPSs) and polymerized whey protein (PWP) as important food functional agents, have not been studied for their combined effects. In this study, the EPS produced by Lactiplantibacillus plantarum HMX2 and PWP were combined in different ratios to prepare EPS-PWP complexes. The results showed that addition of EPS-PWP4 complex (1:5) was most effective in promoting yogurt fermentation to form elastic gel. The EPS-PWP4 yogurt was shown with the best texture in terms of yogurt viscosity, adhesiveness, cohesiveness and water-holding capacity, as well as the least susceptibility to syneresis of yogurt. Analysis of particle sizes demonstrated the smallest particle size and more uniform size distribution in the EPS-PWP4 yogurt with the lowest values of D[4,3] and D90. EPS-PWP4 yogurt was also determined with a higher viable LAB count (8.59 ± 0.03 log CFU/mL) and the best sensory quality. The results suggested that the EPS and PWP could interact in yogurt to promote formation of fine and smooth gel, which provided a novel approach for the improvement of yogurt quality.