Papillary thyroid carcinoma (PTC) is the most common type of thyroid cancer (TC). In a subgroup of patients with PTC, the disease progresses to an invasive stage or in some cases to distant organ metastasis. At present, there is an unmet clinical and diagnostic need for early identification of patients with PTC who are at risk of disease progression or metastasis. In this study, we report several molecular leads and potential biomarker candidates of PTC metastasis for further translational research. The study design was based on comparisons of PTC in three different groups using cross-sectional sampling: Group 1, PTC localized to the thyroid (n = 20); Group 2, PTC with extrathyroidal progression (n = 22); and Group 3, PTC with distant organ metastasis (n = 20). Global transcriptome and microRNAs (miRNA) analyses were conducted using an initial screening set comprising nine formalin-fixed paraffin-embedded PTC samples obtained from three independent patients per study group. The findings were subsequently validated by quantitative real-time polymerase chain reaction (qRT-PCR) using the abovementioned independent patient sample set (n = 62). Comparative analyses of differentially expressed miRNAs showed that miR-193-3p, miR-182-5p, and miR-3607-3p were novel miRNAs associated with PTC metastasis. These potential miRNA biomarkers were associated with TC metastasis and miRNA-target gene associations, which may provide important clinicopathological information on metastasis. Our findings provide new molecular leads for further translational biomarker research, which could facilitate the identification of patients at risk of PTC disease progression or metastasis.