Starch, conformed by amylose and amylopectin, represents the major carbohydrate macromolecule consumed globally as a major component of staple foods. Phenolic compounds are ubiquitous secondary metabolites in plants with strong antioxidant capacities and have attracted a great deal of attention in recent decades. Besides these capabilities, polyphenols are known to interact through different bonds with polysaccharides, lipids or proteins, which impact the formed complex structure and its digestibility. Due to their hydroxyl groups, it appears as if lower MW polyphenols tend to display fewer H-bonds due to their fewer hydroxyl groups and thus weaker interactions and affinity, whereas higher MW polyphenols, such as polymerized tannins and especially proanthocyanidins, display a higher number of available H-bonds and a generally higher affinity. Native starch is usually present in two main forms: V-type inclusion complexes with hydrophobic bonds or non-inclusion crystal complexes (A- or B-type) prone to H-bonds and ionic/electrostatic interactions. The formation of the complexes depends on the starch microstructure, and also depends on the amylose/amylopectin ratio, and the ratio of crystalline and amorphous structures, with polyphenols showing higher affinity towards amylose and the hydrophobic interior of helix structures in starch. At the microstructural level, starch–polyphenol complexation leads to increased porosity and denser granules. At the rheological level, this translates into the starch showing reduced viscosity and elasticity. Moreover, this greatly impairs starch's gelatinization and retrogradation during cooking, providing a final structure more akin to resistant starch, with a final reduced hardness and adhesiveness. These changes affect the digestibility of starch by amylolytic enzymes (i.e. α-amylase) and lead to lowered glucose release from it and absorption. This review aims to present a comprehensive and summarized overview of updated knowledge on this and the remaining gaps in knowledge.