A large variety of molecular pathways in melanoma progression suggests that no individual molecular alteration is crucial in itself. Our aim was to define the molecular alterations underlying metastasis formation. Gene expression profiling was performed using microarray and qRT-PCR to define alterations between matched primary and metastatic melanoma cell lines. These data were integrated with publicly available unmatched tissue data. The invasiveness of cell lines was determined by Matrigel invasion assays and invasive clones from primary melanoma-derived cell lines were also selected. Two metastatic cell line models were created: the regional lymph node WM983A-WM983A-WM983B and the distant lung WM793B-WM793B-1205Lu metastatic models. The majority of metastasis genes were downregulated and enriched in adhesion and ITGA6-B4 pathways. Upregulation of immune pathways was characteristic of distant metastases, whereas increased Rap1 signaling was specific for regional (sub)cutaneous metastases. qRT-PCR analysis of selected integrins (A2, A3, A4, A9, B5, B8, A6, B1, and B3) highlighted the possible importance of ITGA3/4 and B8 in the metastatic process, distinguishing regional and distant metastases. We identified functionally relevant gene clusters that influenced metastasis formation. Our data provide further evidence that integrin expression patterns may be important in distant metastasis formation.