A fundamental event in the development and progression of malignant melanoma is the deregulation of cancer-relevant transcription factors. We recently showed that c-Jun is a main regulator of tumor progression in melanoma and thus the most important member of the AP-1 transcription factor family for this disease. Interestingly, we revealed that c-Jun expression was regulated on the post-transcriptional level and therefore speculated that miRNAs could be involved in c-Jun regulation. We determined seed sequences for miR-125b and miR-527 in the coding region of c-Jun mRNA that hints at the direct involvement of miRNA-dependent regulation on the protein level. We found that the expression of miR-125b was significantly reduced in malignant melanoma cell lines and tissue samples compared with melanocytes, whereas miR-527 remained unchanged. In further functional experiments, treatment of melanoma cells with pre-miR-125b resulted in strong suppression of cellular proliferation and migration, supporting the role of miR-125b in melanoma. In addition, transfection of pre-miR-125b led to strong downregulation of c-Jun protein but not mRNA expression in melanoma cells. Luciferase assays using reporter plasmids containing the miR-125b seed sequence in the luciferase coding region confirmed the direct interaction with miR-125b. Furthermore, immunoprecipitation of Ago-2 revealed that c-Jun mRNA accumulated in the RNA-induced silencing complex after pre-miR-125b transfection in melanoma cells. In summary, we identified an important role for miR-125b in malignant melanoma. Moreover, we demonstrated post-transcriptional regulation of c-Jun by this miRNA and showed that c-Jun is a main mediator of the effects of miR-125b on melanoma cells.