Sedentarism is characterized by low levels of physical activity, a risk factor for obesity and cardio-metabolic diseases. It can also adversely affect the composition and diversity of the gut microbiome which may result in harmful consequences for human health. While cardiorespiratory fitness (CRF) is inversely and independently associated with cardiovascular risk factors and diseases and all-cause mortality, the relationship between low CRF and the gut microbiome is not well known. A total of 3,616 individuals from two independent population-based cohorts of the Study of Health in Pomerania (SHIP-START and SHIP-TREND) performed standardized, symptom-limited cardiopulmonary exercise testing (CPET) and had faecal samples collected to determine gut microbiota profiles (16S rRNA gene sequencing). We analysed cross-sectional associations of CRF with the gut microbiome composition controlling for confounding factors. Lower CRF was associated with reduced microbial diversity, loss of beneficial short-chain fatty acid producing bacteria (i.e. Butyricoccus, Coprococcus, unclassified Ruminococcaceae or Lachnospiraceae) and an increase in opportunistic pathogens such as Escherichia/Shigella, or Citrobacter. Decreased cardiorespiratory performance was associated with a gut microbiota pattern that has been previously related to a proinflammatory state. These associations were independent of body weight or glycemic control.