This work investigates the relationship between the structure and physicochemical properties of three different starches in starch/polyvinyl alcohol aqueous solutions. For this purpose, accurate nuclear magnetic resonance (NMR) analyses were performed to determine the role that the starch structure plays in the formation of binder solutions. Moreover, a dynamic shear rheometer (DSR) was used to investigate the mechanical properties of the solutions and correlate them with the structure of each starch. Complete characterization of the analysed starches and the starch/PVOH solutions was also carried out through light scattering measurements. Furthermore, by crossing the data coming from NMR and light scattering with those coming from rheology, the best solution was identified. Finally, to confirm the interaction mechanism between starch and PVOH, thermogravimetric analysis and an NMR study, using 1H and 13C NMR spectra, were carried out on the film obtained from the best solution. The analyses carried out showed that PVOH has a stabilizing effect on starch/PVOH solutions, and the starch with the greatest branching degree is the one that forms a more structured network.