MicroRNAs (miRs) play a key role in cancer etiology by coordinately repressing numerous target genes involved in cell proliferation, migration and invasion. The genomic region in chromosome 9p21 that encompasses miR-31 is frequently deleted in solid cancers including melanoma; however the expression and functional role of miR-31 has not been previously studied in melanoma. Here, we queried the expression status and performed functional characterization of miR-31 in melanoma tissues and cell lines. We found that down-regulation of miR-31 was a common event in melanoma tumors and cell lines and was associated with genomic loss in a subset of samples. Down-regulation of miR-31 gene expression was also a result of epigenetic silencing by DNA methylation, and via EZH2-mediated histone methylation. Ectopic overexpression of miR-31 in various melanoma cell lines inhibited cell migration and invasion. miR-31 targets include oncogenic kinases such as SRC, MET, NIK (MAP3K14) and the melanoma specific oncogene RAB27a. Furthermore, miR-31 overexpression resulted in down-regulation of EZH2 and a de-repression of its target gene rap1GAP; increased expression of EZH2 was associated with melanoma progression and overall patient survival. Taken together, our study supports a tumor suppressor role for miR-31 in melanoma and identifies novel therapeutic targets.