Single nucleotide polymorphisms, besides influencing susceptibility can potentially alter progression and survival in melanoma patients. In this study we evaluated the association of polymorphisms in the base-excision repair genes XRCC1 and APEX1 with overall survival (OS), metastasis-free survival (MFS) and survival following the first metastasis (SFM) in patients with cutaneous melanoma. We genotyped the D148E APEX1, -77 T>C XRCC1, R280H XRCC1, and R399Q XRCC1 polymorphisms in 400 German melanoma patients (Tx, N0, M0) using an allelic discrimination method. The results were correlated with the patient follow-up parameters. The significant association detected between the R399Q XRCC1 polymorphism and MFS was also evaluated in 529 Spanish melanoma patients. In a Kaplan-Meier survival model the AA genotype of the polymorphism showed a median OS of 24.4 years compared to 11.5 years for two other genotypes. Similarly patients with the AA genotype showed median MFS of 20.9 years compared to 5.3 years for two other genotypes. In a multivariate Cox proportional hazard model, the AA genotype was associated with a hazard ratio (HR) of 0.40, 95% (CI 0.21-0.78, p=0.007) for MFS and 0.32 (95% CI 0.11-0.90, p=0.03) for OS in 400 German melanoma patients. The decreased risk of metastasis was confirmed by adding 529 Spanish melanoma patients with a combined HR of 0.40 (95% CI 0.24-0.68, p=0.0006). A significant association with SFM was also found for -77 T>C XRCC1 (HR 1.73, 95% CI 1.02-2.94, p=0.04). Our results show that non-synonymous variants or those located in potential regulatory regions of DNA repair genes probably influence the disease outcome in melanoma patients and have potentially significant implications for patient surveillance and tailored treatment.