Starch–polyphenol interactions play a critical role in regulating the structural organization and thermal behavior of starch-based systems. In this study, maize starches with different amylose contents were used to systematically investigate how tea polyphenol (TP) complexation influences starch structure and thermal stability. Starch–TP complexes were prepared under thermal-induced conditions and characterized using thermogravimetric analysis (TGA), differential scanning calorimetry (DSC), X-ray diffraction (XRD), Fourier transform infrared spectroscopy (FTIR), and scanning electron microscopy (SEM). TGA results showed that increasing amylose content slightly reduced the thermal stability of native starches, whereas TP incorporation significantly enhanced thermal resistance, particularly in high-amylose systems. XRD analysis indicated that TP complexation did not affect the crystal structure of starch but led to a pronounced reduction in relative crystallinity, with low-amylose complexes exhibiting predominantly amorphous behavior and high-amylose complexes retaining partial nanocrystalline organization. FTIR spectra revealed reduced short-range molecular order and strengthened hydrogen bonding interactions after TP binding. DSC analysis demonstrated increased gelatinization temperatures accompanied by decreased enthalpy changes, reflecting restricted molecular mobility and delayed solvation of nanocrystalline domains. SEM observations further showed a transition toward denser and more interconnected micro–nano structures with increasing amylose content. Overall, TP preferentially interacts with amylose-rich regions through non-covalent interactions, promoting structural reorganization and enhanced thermal stability of the starch matrix. These findings provide new insight into amylose-dependent starch–polyphenol interactions and offer guidance for designing thermally stable starch-based functional materials.