Telomeric dysfunction is linked to colorectal cancer (CRC) initiation. However, the relationship of normal tissue and tumor telomere lengths with CRC progression, molecular features and prognosis is unclear. Here, we measured relative telomere length (RTL) by real-time quantitative PCR in 90 adenomas (aRTL), 419 stage I-IV CRCs (cRTL) and adjacent normal mucosa (nRTL). Age-adjusted RTL was analyzed against germline variants in telomere biology genes, chromosome instability (CIN), microsatellite instability (MSI), CpG island methylator phenotype (CIMP), TP53, KRAS, BRAF mutations and clinical outcomes. In 509 adenoma or CRC patients, nRTL decreased with advancing age. Female gender, proximal location and the TERT rs2736100 G allele were independently associated with longer age-adjusted nRTL. Adenomas and carcinomas exhibited telomere shortening in 79% and 67% and lengthening in 7% and 15% of cases. Age-adjusted nRTL and cRTL were independently associated with tumor stage, decreasing from adenoma to stage III and leveling out or increasing from stage III to IV, respectively. Cancer MSI, CIMP, TP53, KRAS and BRAF status were not related to nRTL or cRTL. Near-tetraploid CRCs exhibited significantly longer cRTLs than CIN- and aneuploidy CRCs, while cRTL was significantly shorter in CRCs with larger numbers of chromosome breaks. Age-adjusted nRTL, cRTL or cRTL:nRTL ratios were not associated with disease-free or overall survival in stage II/III CRC. Taken together, our data show that both normal mucosa and tumor RTL are independently associated with CRC progression, and highlight divergent associations of CRC telomere length with tumor CIN profiles.