Hepatocyte growth factor-overexpressing mice that harbor a deletion of the Ink4a/p16 locus (HP mice) form melanomas with low metastatic potential in response to UV irradiation. Here we report that these tumors become highly metastatic following hemizygous deletion of the Nme1 and Nme2 metastasis suppressor genes (HPN mice). Whole-genome sequencing of melanomas from HPN mice revealed a striking increase in lung metastatic activity that is associated with missense mutations in eight signature genes (Arhgap35, Atp8b4, Brca1, Ift172, Kif21b, Nckap5, Pcdha2, and Zfp869). RNA-seq analysis of transcriptomes from HP and HPN primary melanomas identified a 32-gene signature (HPN lung metastasis signature) for which decreased expression is strongly associated with lung metastatic potential. Analysis of transcriptome data from The Cancer Genome Atlas revealed expression profiles of these genes that predict improved survival of patients with cutaneous or uveal melanoma. Silencing of three representative HPN lung metastasis signature genes (ARRDC3, NYNRIN, RND3) in human melanoma cells resulted in increased invasive activity, consistent with roles for these genes as mediators of the metastasis suppressor function of NME1 and NME2. In conclusion, our studies have identified a family of genes that mediate suppression of melanoma lung metastasis, and which may serve as prognostic markers and/or therapeutic targets for clinical management of metastatic melanoma.