Hair, skin and eye colors are highly heritable and visible traits in humans. We carried out a genome-wide association scan for variants associated with hair and eye pigmentation, skin sensitivity to sun and freckling among 2,986 Icelanders. We then tested the most closely associated SNPs from six regions--four not previously implicated in the normal variation of human pigmentation--and replicated their association in a second sample of 2,718 Icelanders and a sample of 1,214 Dutch. The SNPs from all six regions met the criteria for genome-wide significance. A variant in SLC24A4 is associated with eye and hair color, a variant near KITLG is associated with hair color, two coding variants in TYR are associated with eye color and freckles, and a variant on 6p25.3 is associated with freckles. The fifth region provided refinements to a previously reported association in OCA2, and the sixth encompasses previously described variants in MC1R.