Cachexia is associated with decreased survival in cancer patients and has a prevalence of up to 80%. The etiology of cachexia is poorly understood, and limited treatment options exist. Here, we investigated the role of the human gut microbiome in cachexia by integrating shotgun metagenomics and plasma metabolomics of 31 lung cancer patients. The cachexia group showed significant differences in the gut microbial composition, functional pathways of the metagenome, and the related plasma metabolites compared to non-cachectic patients. Branched-chain amino acids (BCAAs), methylhistamine, and vitamins were significantly depleted in the plasma of cachexia patients, which was also reflected in the depletion of relevant gut microbiota functional pathways. The enrichment of BCAAs and 3-oxocholic acid in non-cachectic patients were positively correlated with gut microbial species Prevotella copri and Lactobacillus gasseri, respectively. Furthermore, the gut microbiota capacity for lipopolysaccharides biosynthesis was significantly enriched in cachectic patients. The involvement of the gut microbiome in cachexia was further observed in a high-performance machine learning model using solely gut microbial features. Our study demonstrates the links between cachectic host metabolism and specific gut microbial species and functions in a clinical setting, suggesting that the gut microbiota could have an influence on cachexia with possible therapeutic applications.