To search for new sequence variants that confer risk of cutaneous basal cell carcinoma (BCC), we conducted a genome-wide SNP association study of 930 Icelanders with BCC and 33,117 controls. After analyzing 304,083 SNPs, we observed signals from loci at 1p36 and 1q42, and replicated these associations in additional sample sets from Iceland and Eastern Europe. Overall, the most significant signals were from rs7538876 on 1p36 (OR = 1.28, P = 4.4 x 10(-12)) and rs801114 on 1q42 (OR = 1.28, P = 5.9 x 10(-12)). The 1p36 locus contains the candidate genes PADI4, PADI6, RCC2 and ARHGEF10L, and the gene nearest to the 1q42 locus is the ras-homolog RHOU. Neither locus was associated with fair pigmentation traits that are known risk factors for BCC, and no risk was observed for melanoma. Approximately 1.6% of individuals of European ancestry are homozygous for both variants, and their estimated risk of BCC is 2.68 times that of noncarriers.