Despite its indolent course, one-third of the papillary thyroid carcinoma (PTC) cases relapses, which directly impact on the quality of patients' lives. The molecular predictors of recurrence of PTC are poorly defined. We aimed at evaluating the long-term (10-20 years) prognostic value of aggressiveness markers in advanced PTC. To this end, immunohistochemistry for BRAFV600E, Estrogen receptor α, Progesterone receptor, Ki-67, and E-cadherin were performed in 53 primary advanced PTC from an up to 20 years follow-up patients from a well-characterized Brazilian cohort. Categorical data were summarized using frequencies and groups were compared using Chi-squared and Fisher's exact tests. The expressions of the aggressiveness markers were associated with clinical-pathological data using the single-covariate logistic regression analysis. The Kaplan-Meier method with the Log-rank and Peto tests was used to estimate the probability of PTC-free survival. Persistence and recurrence (active disease) were associated with age (≥55 years), tumor size (>2 cm), extrathyroidal extension, local aggressiveness, macroscopic lymph node metastasis, and TNM stage at initial treatment. The BRAFV600E mutation status was associated with extrathyroidal extension, local aggressiveness, and inversely associated with distant metastasis at initial treatment. All progesterone receptor-positive patients had active disease and displayed a shorter time of PTC-free survival than the negative ones using the Kaplan-Meir analysis (p = 0.001, Log Rank; p = 0.005, Peto). Loss of E-cadherin expression was associated with an increase in the probability of active disease (OR = 3.75). BRAFV600E could be useful as a biomarker of local aggressiveness, while PR positive and E-cadherin loss of expression could predict the recurrence of advanced PTC.