Abstract Objective: In this study, crucial genes and microRNAs (miRNAs) associated with the progression, staging, and prognosis of papillary thyroid cancer (PTC) were identified. Methods: Four PTC datasets, including our own mRNA-sequencing (mRNA-seq) dataset and three public datasets downloaded from Gene Expression Omnibus and The Cancer Genome Atlas, were used to analyze differentially expressed genes (DEGs) and miRNAs (DEMs) between PTC tumor tissues and paired normal tissues (control). Gene ontology (GO) terms and pathways associated with these DEGs were identified, and protein-protein interactions (PPIs) were analyzed. Additionally, an miRNA-mRNA regulatory network was constructed and the functions of DEMs were explored. Finally, miRNAs/mRNAs associated with tumor staging and prognosis were identified. The expression levels of several key genes and miRNAs were validated by qRT-PCR. Results: Numerous DEGs and DEMs were identified between tumor and control groups in four datasets. The DEGs were significantly enriched in cell adhesion and cancer-related GO terms and pathways. In the constructed PPI network, ITGA2, FN1, ICAM1, TIMP1 and CDH2 were hub proteins. In the miRNA-mRNA negative regulatory networks, miR-204-5p regulated the largest number of target genes, such as TNFRSF12A. miR-146b, miR-204, miR-7-2, and FN1 were associated with tumor stage in PTC, and TNFRSF12A and CLDN1 were related to prognosis. Conclusions: Our results suggested the important roles of ITGA2, FN1, ICAM1, TIMP1 and CDH2 in the progression of PTC. miR-204-5p, miR-7-2, and miR-146b are potential biomarkers for PTC staging and FN1, CLDN1, and TNFRSF12A may serve as markers of prognosis in PTC.