The effects of non-covalent interactions between gallic acid (GA) and starch on starch digestibility and supramolecular structural changes (short-range ordered molecular structure, crystalline structure, lamellar structure and fractal structure) were investigated. The results indicated that the digestibility of both starches was substantially reduced in the rapidly digestible starch (RDS) content, but resistant starch (RS) was increased after interacting with GA. The RS content of starch-GA complexes ranged from 17.70 to 50.02%, which is much higher than that of high amylose starch (G50) (11.11%) and normal maize starch (NMS) (4.46%). Compared with native starches, starch-GA complexes possess more ordered and compact structures; furthermore, G50-GA complexes possessed more compact scattering objects, thicker crystalline lamellae and thinner amorphous lamellae than those of NMS-GA complexes. This revealed that more ordered multi-scale structures promote the RS formation. Docking studies were conducted to reveal the mechanism of digestibility variations. It showed that GA would non-covalently interact with starch molecules and contribute to ordered structure formation to somewhat extent; meanwhile, GA had higher binding affinities to α-amylase than to starch chains; during the hydrolytic process, GA could be released from the complex and was more likely to occupy the active sites of Asp197, Asp300, His299 and Glu233 by hydrogen bonds and van der Waals forces, which kept starch out of the active site pocket and reduced starch digestibility. These results demonstrate that the non-covalent interactions between GA and starch could be a promising method of controlling starch structures and starch digestion behaviors.