Polyphenols may modulate gut microbiota; however, limited studies have examined this relationship relative to obesity. We aim to investigate the association between polyphenol intake and gut microbiota composition in relation to obesity indices among Saudi Arabian females. This study included 92 adults stratified by body mass index (BMI) into controls (BMI ≥ 18.5–24.9 kg/m2; n = 48) and cases (BMI ≥ 30.0 kg/m2; n = 44), and further divided into high and low polyphenol intake by median intake (252 mg/1000 kcal/day). Fecal samples were collected to analyze the gut microbiota composition via the whole-genome shotgun sequencing technique. Results showed that Flavonifractor plautii and Clostridium bolteae were positively correlated with polyphenol intake in the total sample (r = 0.22, p = 0.03; r = 0.28, p = 0.01, respectively). There were inverse correlations between Blautia wexlerae and polyphenol intake (r = −0.56, p < 0.01) in the case group, and between Bacteroides thetaiotaomicron and polyphenol intake (r = −0.45, p = 0.03) in the control group. Those in the case group with low polyphenol intake, and those with high waist-to-hip ratio (WHR; ≥0.83), showed significantly lower alpha-diversity than those in the control group with normal WHR (<0.83), (p < 0.05). Findings suggest that polyphenols are correlated with specific bacteria and may play an important role in the modulation of gut microbiota and obesity management.