Background The tall cell variant of papillary thyroid carcinoma (PTC) is as an aggressive histological variant. The proportion of tall cells needed to influence prognosis is debated. Methods Patients with PTC and tall cells, defined as having a height-to-width ratio of ≥ 3:1, seen at a high-volume center between 2001 and 2015, were reviewed. Specimens were classified as (1) focal tall cell change, containing < 30% of tall cells; (2) tall cell variant, ≥ 30% of tall cells; and (3) control cases selected from infiltrative classical PTCs without adverse cytologic features. Univariate, sensitivity, and multivariate analyses were performed with persistent/recurrent disease as the primary outcome. Results We identified 96 PTCs with focal tall cell change, 35 with the tall cell variant and 104 control cases. Factors associated with poor clinical prognosis were significantly greater in those with focal tall cell change and tall cell variants. Regarding primary outcome, hazard ratios were 2.3 (95% confidence interval CI 1.0–5.7) for focal tall cell change, and 3.4 (95% CI 1.2–8.7) for tall cell variants compared with controls. Five-year disease-free survival was higher for the control group (92.7%, CI 87.4–98.0) compared with focal tall cell change (76.3%, CI 66.1–86.5) and the tall cell variant (62.2%, CI 43.2–81.2). When stratified in groups consisting of tall cell proportions (< 10%, 10–19%, 20–29% and ≥ 30%), identification of ≥ 10% tall cell change was associated with worse outcome ( p  = 0.002). Conclusions PTCs with ≥ 10% tall cell change have worse prognosis than those without tall cells. Our data indicate that thyroid cancer management guidelines should consider PTCs with focal tall cell change outside of the low-risk classification.