Myalgic encephalomyelitis/chronic fatigue syndrome (ME/CFS) is a complex, debilitating disorder manifesting as severe fatigue and post-exertional malaise. The etiology of ME/CFS remains elusive. Here, we present a deep metagenomic analysis of stool combined with plasma metabolomics and clinical phenotyping of two ME/CFS cohorts with short-term (<4 years, n = 75) or long-term disease (>10 years, n = 79) compared with healthy controls (n = 79). First, we describe microbial and metabolomic dysbiosis in ME/CFS patients. Short-term patients showed significant microbial dysbiosis, while long-term patients had largely resolved microbial dysbiosis but had metabolic and clinical aberrations. Second, we identified phenotypic, microbial, and metabolic biomarkers specific to patient cohorts. These revealed potential functional mechanisms underlying disease onset and duration, including reduced microbial butyrate biosynthesis and a reduction in plasma butyrate, bile acids, and benzoate. In addition to the insights derived, our data represent an important resource to facilitate mechanistic hypotheses of host-microbiome interactions in ME/CFS.