Currently, there is a lack of efficient recurrence prediction methods for papillary thyroid carcinoma (PTC). In this study, we enrolled 202 PTC patients submitted to total thyroidectomy and radioiodine therapy with long-term follow-up (median = 10.7 years). The patients were classified as having favorable clinical outcome (PTC-FCO, no disease in the follow-up) or recurrence (PTC-RE). Alterations in BRAF, RAS, RET, and TERT were investigated (n = 202) and the transcriptome of 48 PTC (>10 years of follow-up) samples was profiled. Although no mutation was associated with the recurrence risk, 68 genes were found as differentially expressed in PTC-RE compared to PTC-FCO. Pathway analysis highlighted a potential role of cancer-related pathways, including signal transduction and FoxO signaling. Among the eight selected genes evaluated by RT-qPCR, SLC2A4 and GADD45B showed down-expression exclusively in the PTC-FCO group compared to non-neoplastic tissues (NT). Increased expression of GADD45B was an independent marker of shorter disease-free survival [hazard ratio (HR) 2.9; 95% confidence interval (CI95) 1.2–7.0] in our cohort and with overall survival in the TCGA dataset (HR = 4.38, CI95 1.2–15.5). In conclusion, GADD45B transcript was identified as a novel prognostic marker candidate in PTC patients treated with total thyroidectomy and radioiodine therapy.