It is unclear to what degree genomic and traditional (phenotypic and environmental) risk factors overlap in their prediction of melanoma risk. We evaluated the incremental contribution of common genomic variants (in pigmentation, nevus, and other pathways) and their overlap with traditional risk factors, using data from two population-based case-control studies from Australia (n = 1,035) and the United Kingdom (n = 1,460) that used the same questionnaires. Polygenic risk scores were derived from 21 gene regions associated with melanoma and odds ratios from published meta-analyses. Logistic regression models were adjusted for age, sex, center, and ancestry. Adding the polygenic risk score to a model with traditional risk factors increased the area under the receiver operating characteristic curve (AUC) by 2.3% (P = 0.003) for Australia and by 2.8% (P = 0.002) for Leeds. Gene variants in the pigmentation pathway, particularly MC1R, were responsible for most of the incremental improvement. In a cross-tabulation of polygenic by traditional tertile risk scores, 59% (Australia) and 49% (Leeds) of participants were categorized in the same (concordant) tertile. Of participants with low traditional risk, 9% (Australia) and 21% (Leeds) had high polygenic risk. Testing of genomic variants can identify people who are susceptible to melanoma despite not having a traditional phenotypic risk profile.