Mycosis fungoides (MF) is the most frequent form of cutaneous T-cell lymphoma. The disease often takes an indolent course, but in approximately one-third of the patients, the disease progresses to an aggressive malignancy with a poor prognosis. At the time of diagnosis, it is impossible to predict which patients develop severe disease and are in need of aggressive treatment. Accordingly, we investigated the prognostic potential of microRNAs (miRNAs) at the time of diagnosis in MF. Using a quantitative reverse transcription polymerase chain reaction platform, we analyzed miRNA expression in diagnostic skin biopsies from 154 Danish patients with early-stage MF. The patients were subdivided into a discovery cohort (n = 82) and an independent validation cohort (n = 72). The miRNA classifier was built using a LASSO (least absolute shrinkage and selection operator) Cox regression to predict progression-free survival (PFS). We developed a 3-miRNA classifier, based on miR-106b-5p, miR-148a-3p, and miR-338-3p, which successfully separated patients into high-risk and low-risk groups of disease progression. PFS was significantly different between these groups in both the discovery cohort and the validation cohort. The classifier was stronger than existing clinical prognostic factors and remained a strong independent prognostic tool after stratification and adjustment for these factors. Importantly, patients in the high-risk group had a significantly reduced overall survival. The 3-miRNA classifier is an effective tool to predict disease progression of early-stage MF at the time of diagnosis. The classifier adds significant prognostic value to existing clinical prognostic factors and may facilitate more individualized treatment of these patients.