Telomere repeats at chromosomal ends, critical to genomic integrity, undergo age-dependent attrition. Telomere length, a polygenic trait, has been associated with risk of several disorders including cancers. In contrast to association of long telomeres with increased risk of several cancers, including melanoma, emerging reports suggest that short telomeres predict poor survival in patients with different cancers. In this study based on 1019 stage I and II cutaneous melanoma patients, we show an association between the patients with short telomeres and poor melanoma-specific survival (HR 2.05, 95% CI 1.33-3.16) compared to patients with long telomeres. Due to inverse correlation between age and telomere length (r -0.19, P < 0.0001), we stratified the patients into quantiles based on age at diagnosis and also carried out age-matched analysis. The effect of short telomeres on survival was determined by using multivariate Cox regression that included composite genetic risk score computed from genotyping of the patients for telomere-length associated polymorphisms. The effect of decreased telomere length on poor melanoma-specific survival was particularly strong in patients within the age quantile below 30 years (HR 3.82, 95% CI 1.10-13.30) and between 30-40 years (HR 2.69, 95% CI 1.03-7.03). Our study shows that in contrast to increased melanoma risk associated with increased telomere length, decreased telomere length predicts poor survival in melanoma subgroups.