The aim of this study was to investigate the association between cardiorespiratory fitness and gut microbiota composition in premenopausal women. The participants consisted of 71 premenopausal Finnish women (aged 19–49 years). Gut microbiota were analyzed using flow cytometry, 16S rRNA gene hybridization and DNA-staining. Maximum oxygen uptake (VO2max) was assessed by respiratory gas analyzer and body composition by Bioimpdance. We found that participants with low VO2max had lower Bacteroides, but higher Eubacterium rectale-Clostridium coccoides than the high VO2max group (p < 0.05 for all). VO2max was inversely associated with EreC (r = −0.309, p = 0.01) but not with other bacteria. VO2max also negatively correlated with fat% (r = −0.755, p < 0.001), triglycerides (r = −0.274, p = 0.021) and leptin (r = −0.574, p < 0.001). By contrast, EreC was positively associated with fat% (r = 0.382, p = 0.002), dietary fat intake (r = 0.258, p = 0.034), triglycerides (r = 0.390, p = 0.002) and leptin (r = 0.424, p = 0.001), but negatively with carbohydrate intake (r = −0.252, p = 0.034) and HDL (r = −0.26, p = 0.028). After adjusting for age and dietary intake, all the significant associations remained. However, after adjusting for fat%, the associations between VO2max and EreC disappeared. Our results suggest that cardiorespiratory fitness is associated with gut microbiota composition, independent of age and carbohydrate or fat intake. The association between VO2max and EreC, however, appears to be mediated by body fatness.