Noninvasive prognostic markers are needed to improve the survival of colorectal cancer (CRC) patients. Toward this goal, we applied untargeted systems glycobiology approaches to snap-frozen and formalin-fixed paraffin-embedded tumor tissues and peripheral blood mononuclear cells from CRC patients spanning different disease stages and matching controls to faithfully uncover molecular changes associated with CRC. Quantitative glycomics and immunohistochemistry revealed that noncanonical paucimannosidic N-glycans are elevated in CRC tumors relative to normal adjacent tissues. Cell origin-focused glycoproteomics enabled using the well-curated Human Protein Atlas combined with immunohistochemistry of CRC tumor tissues recapitulated these findings and indicated that the paucimannosidic proteins were in part from tumor-infiltrating monocytes (e.g., MPO, AZU1) and of CRC cell origin (e.g., LGALS3BP, PSAP). Biosynthetically explaining these observations, N-acetyl-β-D-hexosaminidase (Hex) subunit β (HEXB) was found to be overexpressed in CRC tissues relative to normal adjacent colorectal tissues and colocalization and enzyme inhibition studies confirmed that HEXB facilitates paucimannosidic protein biosynthesis in CRC cells. Employing a sensitive, quick, and robust enzyme activity assay, we then showed that Hex activity was elevated in plasma and peripheral blood mononuclear cells from patients with advanced CRC relative to controls and those with early-stage disease. Surveying a large donor cohort, the plasma Hex activity was found to be raised in CRC patients relative to normal controls and correlated with the 5-year survival of CRC patients indicating that elevated plasma Hex activity is a potential disease risk marker for patient outcome. Our glycoproteomics-driven findings open avenues for better prognostication and disease risk stratification in CRC.