We performed a genome-wide association study of melanoma in a discovery cohort of 2,168 Australian individuals with melanoma and 4,387 control individuals. In this discovery phase, we confirm several previously characterized melanoma-associated loci at MC1R, ASIP and MTAP-CDKN2A. We selected variants at nine loci for replication in three independent case-control studies (Europe: 2,804 subjects with melanoma, 7,618 control subjects; United States 1: 1,804 subjects with melanoma, 1,026 control subjects; United States 2: 585 subjects with melanoma, 6,500 control subjects). The combined meta-analysis of all case-control studies identified a new susceptibility locus at 1q21.3 (rs7412746, P = 9.0 × 10(-11), OR in combined replication cohorts of 0.89 (95% CI 0.85-0.95)). We also show evidence suggesting that melanoma associates with 1q42.12 (rs3219090, P = 9.3 × 10(-8)). The associated variants at the 1q21.3 locus span a region with ten genes, and plausible candidate genes for melanoma susceptibility include ARNT and SETDB1. Variants at the 1q21.3 locus do not seem to be associated with human pigmentation or measures of nevus density.