Purpose: In this proof-of-concept pilot study, our purpose was to determine correlations between gut microbiota composition and alterations in cardiorespiratory fitness and psychosocial outcomes among post-primary treatment breast cancer survivors (BCS). Methods: Composition of the gut microbiota in BCS (n = 12) was assessed at baseline (M0) and at the end of 3 months (M3) using Illumina MiSeq DNA Sequencing of the 16S rRNA gene. Gut microbiota composition was analyzed using the QIIME bioinformatics software and represented through diversity metrics and taxa analyses. Cardiorespiratory fitness, fatigue, anxiety, depression, and sleep dysfunction were assessed at M0 and M3 via the submaximal treadmill test, Fatigue Symptom Inventory, Hospital Anxiety and Depression Scale, and Pittsburgh Sleep Quality Index, respectively. Results: Increased fatigue interference in BCS was associated with increased mean within-sample Shannon diversity (organism richness and evenness) (p = 0.009). Weighted UniFrac analysis (shifts in taxa relative abundance) revealed significant differences in between-sample (beta) diversity for changes in fatigue interference (p = 0.01) and anxiety (p = 0.022), with a trend observed for fatigue intensity and sleep dysfunction (p < 0.1). Unweighted UniFrac analysis (shifts in taxa types) found significant beta diversity differences for cardiorespiratory fitness (p = 0.026). Prior to false discovery correction (FDR), changes in fitness, fatigue, anxiety, and sleep dysfunction were associated with the frequency of certain gut bacteria genera (e.g., Faecalibacterium, Prevotella, Bacteroides) (p < 0.05). Conclusions: Correlations may exist between alterations in gut microbiota composition and longitudinal changes in cardiorespiratory fitness, fatigue, and anxiety in BCS. Further research examining the role of the microbiota-gut-brain axis in exercise-induced effects on psychosocial outcomes in BCS is warranted.