Several studies have focused on identifying microRNAs involved in the pathogenesis of melanoma. However, its association with clinicopathological features has been scarcely addressed. The aim of this study is to identify microRNAs expression profiles related to aggressive clinicopathological and molecular features, and to analyze the association with melanoma survival. A retrospective and observational study was performed in a series of 179 formalin-fixed paraffin embedded primary cutaneous melanomas. First, a screening analysis on a discovery set (n = 22) using miRNA gene chip array (Affymetrix, Santa Clara, California, USA) was performed. Differentially expressed microRNAs were detected employing the software Partek Genomic Suite. Validation of four microRNAs was subsequently performed in the entire series (n = 179) by quantitative real time PCR (qRT-PCR). MicroRNAs expression screening analysis identified 101 microRNAs differentially expressed according to Breslow thickness (≤1 mm vs. >1 mm), 79 according to the presence or absence of ulceration, 78 according to mitosis/mm2 (<1 mitosis vs. ≥1 mitosis) and 97 according to the TERT promoter status (wt vs. mutated). Six microRNAs (miR-138-5p, miR-130b-3p, miR-30b-5p, miR-34a-5p, miR-500a-5p, miR-339-5p) were selected for being validated by qRT-PCR in the discovery set (n = 22). Of those, miR-138-5p, miR-130b-3p, miR-30b-5p, miR-34a-5p were selected for further analysis in the entire series (n = 179). Overexpression of miR-138-5p and miR-130b-3p was significantly associated with greater Breslow thickness, ulceration, and mitosis. TERT mutated melanomas overexpressed miR-138-5p. Kaplan–Meier survival analysis showed poorer survival in melanomas with miR-130b-3p overexpression. Our findings provide support for the existence of a microRNA expression profile in melanomas with aggressive clinicopathological features and poor prognosis.