Papillary thyroid cancer (PTC) can be divided into classical variant of PTC (cPTC), follicular variant of PTC (fvPTC), and tall cell variant (tcPTC). These variants differ in their histopathology and cytology; however, their molecular background is not clearly understood. Our results shed some new light on papillary thyroid cancer biology as new direct miRNA-gene regulations are discovered. The Cancer Genome Atlas (TCGA) 466 thyroid cancer samples were studied in parallel datasets to discover potential miRNA-mRNA regulations. Additionally, miRNAs and genes differentiating PTC variants (cPTC, fvPTC, and tcPTC) were indicated. Putative miRNA regulatory pairs were discovered: hsa-miR-146b-5p with PHKB and IRAK1, hsa-miR-874-3p with ITGB4 characteristic for classic PTC samples, and hsa-miR-152-3p with TGFA characteristic for follicular variant PTC samples. MiRNA-mRNA regulations discovery opens a new perspective in understanding of PTC biology. Furthermore, our successful pipeline of miRNA-mRNA regulatory pathways discovery could serve as a universal tool to find new miRNA-mRNA regulations, also in different datasets.