This study aimed to identify microRNA species involved in the earliest metastatic event in cutaneous malignant melanoma (MM). Samples from 28 patients with MM [stage T2 (tumor), M0 (distant metastasis)] were grouped by the presence of micrometastasis in the sentinel lymph nodes (N0/N1). Melanoma cells were harvested from primary, cutaneous MM tumors by laser-capture microdissection, and microRNA expression profiles were obtained by the microarray technique. Results were validated by quantitative reverse transcription PCR. We found that miR-125b was downregulated in the primary cutaneous melanomas that produced early metastases (T2, N1, M0) compared with the sentinel lymph node-negative (T2, N0, M0) melanomas. MiR-125b has earlier been found to be downregulated in other tumor types and in atypic naevi compared with the common acquired naevi. In conclusion, miR-125b may be involved in an early progression of cutaneous MM.