Genistein (Gen) and exercise (Exe) have been postulated as potential strategies to ameliorate obesity, inflammation, and gut microbiota (GM) with promising results. However, the impact of the combination of both Exe and Gen is yet to be investigated. We aimed to analyze the impacts of Exe, Gen, and their combined effects on GM and inflammation in mice after a 12-week high-fat, high-sugar diet (HFD). Eighty-three C57BL/6 mice were randomized to control, HFD, HFD + Exe, HFD + Gen, or HFD + Exe + Gen. The V4 region of the 16S rRNA gene was analyzed with Illumina MiSeq. Serum samples were used to analyze interleukin (Il)-6 and Tumor Necrosis Factor alpha (TNF-alpha). The HFD + Exe and HFD + Exe + Gen treatments resulted in significantly greater microbial richness compared to HFD. All the treatments had a significantly different impact on the GM community structure. was significantly more abundant after the HFD + Exe + Gen treatment when compared to all the other HFD groups. Exe + Gen resulted in serum Il-6 concentrations similar to that of controls. TNF-alpha concentrations did not differ by treatment. Overall, Exe had a positive impact on microbial richness, and might be the driving bacteria for the GM structure differences. Exe + Gen may be an effective treatment for preventing HFD-induced inflammation.