The beneficial effects of physical activity (PA) on gut microbiome have been reported, nevertheless the findings are inconsistent, with the main limitation of subjective methods for assessing PA. It is well accepted that using an objective assessment of PA reduces the measurement error and also allows objective assessment of sedentary behavior (SB). We aimed to study the associations between accelerometer-assessed behaviors (i.e., SB, light-intensity physical activity [LPA] and moderate-to-vigorous physical activity [MVPA]) with the gut microbiome using compositional data analysis, a novel approach that enables to study these behaviors accounting for their inter-dependency. This cross-sectional study included 289 women from the Northern Finland Birth Cohort 1966. Physical activity was measured during 14 days by wrist-worn accelerometers. Analyses based on the combined effect of MVPA and SB, and compositional data analyses in association with the gut microbiome data were performed. The microbial alpha- and beta-diversity were not significantly different between the MVPA-SB groups, and no differentially abundant microorganisms were detected. Compositional data analysis did not show any significant associations between any movement behavior (relative to the others) on microbial alpha-diversity. Butyrate-producing bacteria such as Agathobacter and Lachnospiraceae CAG56 were significantly more abundant when reallocating time from LPA or SB to MVPA (γ = 0.609 and 0.113, both p-values = 0.007). While PA and SB were not associated with microbial diversity, we found associations of these behaviors with specific gut bacteria, suggesting that PA of at least moderate intensity (i.e., MVPA) could increase the abundance of short-chain fatty acid-producing microbes.