Although melanoma is initiated by acquisition of point mutations and limited focal copy number alterations in melanocytes-of-origin, the nature of genetic changes that characterize lethal metastatic disease is poorly understood. We analyzed the evolution of human melanoma progressing from early- to late-stage disease in 13 patients by sampling their tumors at multiple sites and times. Analysis of whole exome and genome sequencing data from more than 80 tumor samples typically revealed only limited gain of point mutations, with net mutational loss in some metastases. In contrast, melanoma evolution was dominated by large-scale aneuploidy and tetraploidization, in which widespread loss of heterozygosity sculpted the burden of point mutations, predicted neoantigens and structural variants even in treatment-naïve and early-stage tumors in some patients. These results imply that dysregulation of genomic integrity is a key driver of selective clonal advantage during melanoma progression.