Gut microbiota has been implicated as a pivotal contributing factor in diet-related obesity; however, its role in development of disease phenotypes in human genetic obesity such as Prader–Willi syndrome (PWS) remains elusive. In this hospitalized intervention trial with PWS (n = 17) and simple obesity (n = 21) children, a diet rich in non-digestible carbohydrates induced significant weight loss and concomitant structural changes of the gut microbiota together with reduction of serum antigen load and alleviation of inflammation. Co-abundance network analysis of 161 prevalent bacterial draft genomes assembled directly from metagenomic datasets showed relative increase of functional genome groups for acetate production from carbohydrates fermentation. NMR-based metabolomic profiling of urine showed diet-induced overall changes of host metabotypes and identified significantly reduced trimethylamine N-oxide and indoxyl sulfate, host-bacteria co-metabolites known to induce metabolic deteriorations. Specific bacterial genomes that were correlated with urine levels of these detrimental co-metabolites were found to encode enzyme genes for production of their precursors by fermentation of choline or tryptophan in the gut. When transplanted into germ-free mice, the pre-intervention gut microbiota induced higher inflammation and larger adipocytes compared with the post-intervention microbiota from the same volunteer. Our multi-omics-based systems analysis indicates a significant etiological contribution of dysbiotic gut microbiota to both genetic and simple obesity in children, implicating a potentially effective target for alleviation.