Cancer of unknown primary (CUP) represents a common and important clinical problem. There is evidence that most CUPs are metastases of carcinomas whose primary site cannot be recognized. Driven by the hypothesis that the knowledge of primary cancer could improve patient’s prognosis, we investigated microRNA expression profiling as a tool for identifying the tissue of origin of metastases. We assessed microRNA expression from 101 formalin-fixed, paraffin-embedded (FFPE) samples from primary cancers and metastasis samples by using a microarray platform. Forty samples representing ten different cancer types were used for defining a cancer-type-specific microRNA signature, which was used for predicting primary sites of metastatic cancers. A 47-miRNA signature was identified and used to estimate tissue-of-origin probabilities for each sample. Overall, accuracy reached 100% for primary cancers and 78% for metastases in our cohort of samples. When the signature was applied to an independent published dataset of 170 samples, accuracy remained high: correct prediction was found within the first two options in 86% of the metastasis cases (first prediction was correct in 68% of cases). This signature was also applied to predict 16 CUPs. In this group, first predictions exhibited probabilities higher than 90% in most of the cases. These results establish that FFPE samples can be used to reveal the tissue of origin of metastatic cancers by using microRNA expression profiling and suggest that the approach, if applied, could provide strong indications for CUPs, whose correct diagnosis is presently undefined.