Background Recurrence of papillary thyroid cancer is not uncommon, but incorporating clinicopathologic parameters to predict recurrence is suboptimal. The aim of this study was to identify systemically recurrence-associated genes using The Cancer Genome Atlas RNA sequencing database. Methods A total of 504 patients with transcriptome sequencing data of the primary neoplasm were included in this study. High and low levels of expression of each gene were defined by median splits. Differences in recurrence-free survival were compared using Kaplan-Meier curves and log-rank tests. Recurrence-associated genes were subjected to functional enrichment analyses with Kyoto Encyclopedia of Genes and Genomes annotation databases and Ingenuity Pathway Analysis. Results We found that 1,807 genes were associated with recurrence-free survival. There were 676 genes of which high expression was associated with a greater risk of recurrence. These genes were enriched in pathways involved in cell cycle regulation and DNA repair. Among 1,131 genes of which low expression was associated with recurrence, Kyoto Encyclopedia of Genes and Genomes–annotated functions were metabolism, calcium signaling, glycan biosynthesis, and the Notch signaling pathway. Canonical pathways identified by Ingenuity Pathway Analysis included RXR function, nitric oxide signaling, interleukin-8 signaling, and nutrient sensing. In addition, low expression of the majority of thyroid differentiation genes was associated with a significantly less recurrence-free survival. Conclusion Upregulation of cell cycle–regulating and DNA repair genes appears to have a negative impact on recurrence-free survival in patients with papillary thyroid cancer. Furthermore, recurrence is associated with thyroid dedifferentiation.