Cancer mortality is exacerbated by late-stage diagnosis. Liquid biopsies based on genomic biomarkers can noninvasively diagnose cancers. However, validation studies have reported ~10% sensitivity to detect stage I cancer in a screening population and specific types, such as brain or genitourinary tumors, remain undetectable. We investigated urine and plasma free glycosaminoglycan profiles (GAGomes) as tumor metabolism biomarkers for multi-cancer early detection (MCED) of 14 cancer types using 2,064 samples from 1,260 cancer or healthy subjects. We observed widespread cancer-specific changes in biofluidic GAGomes recapitulated in an in vivo cancer progression model. We developed three machine learning models based on urine (Nurine = 220 cancer vs. 360 healthy) and plasma (Nplasma = 517 vs. 425) GAGomes that can detect any cancer with an area under the receiver operating characteristic curve of 0.83-0.93 with up to 62% sensitivity to stage I disease at 95% specificity. Undetected patients had a 39 to 50% lower risk of death. GAGomes predicted the putative cancer location with 89% accuracy. In a validation study on a screening-like population requiring ≥ 99% specificity, combined GAGomes predicted any cancer type with poor prognosis within 18 months with 43% sensitivity (21% in stage I; N = 121 and 49 cases). Overall, GAGomes appeared to be powerful MCED metabolic biomarkers, potentially doubling the number of stage I cancers detectable using genomic biomarkers.