Introduction The incidence of papillary thyroid microcarcinoma (PTMC) has increased, and its treatment remains controversial. Objective To identify the clinical and pathological factors predictive of tumor recurrence. Methods We retrospectively analyzed 2,538 consecutive patients treated for PTMC, most submitted to total thyroidectomy (98%) followed by radioactive iodine (RAI) ablation (51.7%) at a cancer center from 1996 to 2015. The patients were stratified according to the American Thyroid Association (ATA) risk categories (low, intermediate, or high), and the clinicopathological features were evaluated by multivariate Cox regression analysis to identify independent prognostic factors for recurrence. Results After a mean follow-up of 58 months (range: 3 to 236.5 months), tumor recurrence was diagnosed in 63 (2.5%) patients, mostly in the lymph nodes. Distant metastasis occurred in 2 (0.1%) patients. There were no cancer-related deaths. The multivariate analysis showed that age < 55 years (p = 0.049; hazard ratio [HR]: 2.54; 95% confidence interval [95%CI]: 0.95 to 0.99), multifocality (p = 0.032; HR: 1.76; 95%CI: 1.05 to 2.96), and the presence of lymph-node metastasis (p < 0.001; HR: 3.69; 95%CI: 2.07-6.57) were independent risk factors for recurrence. Recurrence was observed in 29 (1.5%) out of 1,940 low-risk patients, 32 (5.4%) out of 590 intermediate-risk patients, and in 2 (25%) out of 8 high-risk patients. Conclusions The prognosis of PTMC is excellent, favoring a conservative treatment for most patients. Age < 55 years, multifocality, and node metastasis at diagnosis, as well the ATA staging system effectively predict the risk of recurrence. The presence of these risk factors can help identify patients who should be considered for more aggressive management and more frequent follow-up.