Metastases are the major cause of cancer-related deaths, but the mechanisms of the metastatic process remain poorly understood. In recent years, the involvement of microRNAs (miRNAs) in cancer has become apparent, and the objective of this study was to identify miRNAs associated with breast cancer progression. Global miRNA expression profiling was performed on 47 tumor samples from 14 patients with paired samples from primary breast tumors and corresponding lymph node and distant metastases using LNA-enhanced miRNA microarrays. The identified miRNA expression alterations were validated by real-time PCR, and tissue distribution of the miRNAs was visualized by in situ hybridization. The patients, in which the miRNA profile of the primary tumor and corresponding distant metastasis clustered in the unsupervised cluster analysis, showed significantly shorter intervals between the diagnosis of the primary tumor and distant metastasis (median 1.6 years) compared to those that did not cluster (median 11.3 years) (p < 0.003). Fifteen miRNAs were identified that were significantly differentially expressed between primary tumors and corresponding distant metastases, including miR-9, miR-219-5p and four of the five members of the miR-200 family involved in epithelial-mesenchymal transition. Tumor expression of miR-9 and miR-200b were confirmed using in situ hybridization, which also verified higher expression of these miRNAs in the distant metastases versus corresponding primary tumors. Our results demonstrate alterations in miRNA expression at different stages of disease progression in breast cancer, and suggest a direct involvement of the miR-200 family and miR-9 in the metastatic process.