Background: Variation in the human fecal microbiota has previously been associated with body mass index (BMI). Although obesity is a global health burden, the accumulation of abdominal visceral fat is the specific cardio-metabolic disease risk factor. Here, we explore links between the fecal microbiota and abdominal adiposity using body composition as measured by dual-energy X-ray absorptiometry in a large sample of twins from the TwinsUK cohort, comparing fecal 16S rRNA diversity profiles with six adiposity measures. Results: We profile six adiposity measures in 3666 twins and estimate their heritability, finding novel evidence for strong genetic effects underlying visceral fat and android/gynoid ratio. We confirm the association of lower diversity of the fecal microbiome with obesity and adiposity measures, and then compare the association between fecal microbial composition and the adiposity phenotypes in a discovery subsample of twins. We identify associations between the relative abundances of fecal microbial operational taxonomic units (OTUs) and abdominal adiposity measures. Most of these results involve visceral fat associations, with the strongest associations between visceral fat and Oscillospira members. Using BMI as a surrogate phenotype, we pursue replication in independent samples from three population-based cohorts including American Gut, Flemish Gut Flora Project and the extended TwinsUK cohort. Meta-analyses across the replication samples indicate that 8 OTUs replicate at a stringent threshold across all cohorts, while 49 OTUs achieve nominal significance in at least one replication sample. Heritability analysis of the adiposity-associated microbial OTUs prompted us to assess host genetic-microbe interactions at obesity-associated human candidate loci. We observe significant associations of adiposity-OTU abundances with host genetic variants in the FHIT, TDRG1 and ELAVL4 genes, suggesting a potential role for host genes to mediate the link between the fecal microbiome and obesity. Conclusions: Our results provide novel insights into the role of the fecal microbiota in cardio-metabolic disease with clear potential for prevention and novel therapies.