Animal studies increasingly indicate that the gut microbiota composition and function can be involved in the pathophysiology and progression of Alzheimer’s disease (AD) at multiple levels. However, few studies have investigated this putative gut-brain axis in human beings, and none of them considered diet as a determinant of intestinal microbiota composition. Epidemiological studies highlight that a high intake of fruit and vegetables, such as that typical of the Mediterranean diet, can modulate AD progression. Thus, nutritional interventions are being increasingly studied as a possible non-pharmacological strategy to slow down the progression of AD. In particular, polyphenols and fibers represent the nutritional compounds with the higher potential of counterbalancing the pathophysiological mechanisms of dementia due to their antioxidant, anti-inflammatory, and anti-apoptotic properties. These actions are mediated by the gut microbiota, that can transform polyphenols and fibers into biologically active compounds including, among others, phenyl-γ-valerolactones, urolithins, butyrate, and other short-chain fatty acids. In this review, the complex mechanisms linking nutrition, gut microbiota composition, and pathophysiology of cognitive decline in AD are discussed, with a particular focus on the role of polyphenols and fibers. The gaps between pre-clinical and clinical studies are particularly emphasized, as well as the urgent need for studies comprehensively evaluating the link between nutrition, microbiome, and clinical aspects of AD.