Non-invasive prognostic markers are needed to improve survival of colorectal cancer (CRC) patients. Towards this goal, we here apply integrative systems glycobiology approaches to tumour tissues and PBMCs from CRC patients and matching controls as well as a CRC patient-derived cell line. The untargeted -omics-driven approaches revealed that non-canonical paucimannosidic proteins from monocytic and cancer cell origins are prominent signatures in CRC tumour tissues, and that their expression associates with CRC progression. Guided by these novel relationships, we then show in vitro that N-acetyl-β-D-hexosaminidase (Hex) drives paucimannosidic protein biosynthesis in CRC cells, and is intimately involved in processes underpinning CRC metastasis (adhesion, migration, invasion). Importantly, Hex activity was elevated in PBMCs and plasma from patients with advanced CRC relative to those with early-stage disease. Notably, we show that plasma Hex activity accurately informs on CRC patient survival. Our study opens new avenues for effective prognostication and therapeutic intervention in CRC.