The relationship between telomeres, nevi and melanoma is complex. Shorter telomeres have been found to be associated with many cancers and with number of nevi, a known risk factor for melanoma. However, shorter telomeres have also been found to decrease melanoma risk. We performed a systematic analysis of telomere-related genes and tagSNPs within these genes, in relation to the risk of melanoma, dysplastic nevi, and nevus count combining data from four studies conducted in Italy. In addition, we examined whether telomere length measured in peripheral blood leukocytes is related to the risk of melanoma, dysplastic nevi, number of nevi, or telomere-related SNPs. A total of 796 cases and 770 controls were genotyped for 517 SNPs in 39 telomere-related genes genotyped with a custom-made array. Replication of the top SNPs was conducted in two American populations consisting of 488 subjects from 53 melanoma-prone families and 1,086 cases and 1,024 controls from a case-control study. We estimated odds ratios for associations with SNPs and combined SNP P-values to compute gene region-specific, functional group-specific, and overall P-value using an adaptive rank-truncated product algorithm. In the Mediterranean population, we found suggestive evidence that RECQL4, a gene involved in genome stability, RTEL1, a gene regulating telomere elongation, and TERF2, a gene implicated in the protection of telomeres, were associated with melanoma, the presence of dysplastic nevi and number of nevi, respectively. However, these associations were not found in the American samples, suggesting variable melanoma susceptibility for these genes across populations or chance findings in our discovery sample. Larger studies across different populations are necessary to clarify these associations.