Abstract Background The ingestion of a high-fat diet (HFD) and the resulting obese state can exert a multitude of stressors on the individual including anxiety and cognitive dysfunction. Though many studies have shown that exercise can alleviate the negative consequences of a HFD using metabolic readouts such as insulin and glucose, a paucity of well-controlled rodent studies have been published on HFD and exercise interactions with regard to behavioral outcomes. This is a critical issue since some individuals assume that HFD-induced behavioral problems such as anxiety and cognitive dysfunction can simply be exercised away. To investigate this, we analyzed mice fed a normal diet (ND), ND with exercise, HFD diet, or HFD with exercise. Results We found that mice on a HFD had robust anxiety phenotypes but this was not rescued by exercise. Conversely, exercise increased cognitive abilities but this was not impacted by the HFD. Given the importance of the gut microbiome in shaping the host state, we used 16S rRNA hypervariable tag sequencing to profile our cohorts and found that HFD massively reshaped the gut microbial community in agreement with numerous published studies. However, exercise alone also caused massive shifts in the gut microbiome at nearly the same magnitude as diet but these changes were surprisingly orthogonal. Additionally, specific bacterial abundances were directly proportional to measures of anxiety or cognition. Conclusions Thus, behavioral domains and the gut microbiome are both impacted by diet and exercise but in unrelated ways. These data have important implications for obesity research aimed at modifications of the gut microbiome and suggest that specific gut microbes could be used as a biomarker for anxiety or cognition or perhaps even targeted for therapy.