Preoperative vocal cord palsy (VCP) may indicate locally invasive papillary thyroid cancer (PTC); using this relationship, we evaluated the clinical outcomes and risk factors for recurrence in post-thyroidectomy T4a PTC patients with recurrent laryngeal nerve (RLN) involvement. We retrospectively investigated thyroidectomy patients, recorded their clinical factors, recurrence rate, and pathological findings, and analysed the relationship between recurrence rate and clinical factors. Of 72 patients, 37 (51%) had preoperative VCP and 35 (49%) had normal preoperative vocal cord movement with confirmed intraoperative RLN invasion. Tracheal and esophageal invasion was observed in 13 (18%) and 15 (21%) patients, respectively. Thyroid cancer recurred in 18 (25%) patients over 58 months, resulting in 2 (3%) deaths. Recurrence was not associated with surgical extent, organ invasion, enlarged tumour size, or lymph node infiltration (p > 0.05). The recurrence rate was significantly higher in patients with positive resection margins (p < 0.05). T4a PTC patients with RLN involvement showed a poor prognosis. The recurrence rate was not affected by preoperative VCP, intraoperative detection of RLN invasion, nerve resection, nerve preservation by shaving, lymph node metastasis, or tracheal or esophageal invasion. The most important prognostic factor for recurrence was a positive resection margin.