There are no established prognostic factors or standardized therapies for hepatocellular carcinoma (HCC) recurrence in liver transplantation (LT). The aim of this study was to investigate impact of underlying patient condition on treatment and outcomes of recurrence of HCC after LT. The medical records of 268 LT patients with HCC were evaluated. Potential prognostic factors for survival after recurrence were evaluated, including recurrent tumor characteristics, medical/radiological/surgical therapies for recurrence, and an inflammatory marker (neutrophil/lymphocyte ratio). Laboratory tests at recurrence, including albumin, absolute lymphocyte count (ALC), prognostic nutritional index (PNI: ALC(/μL) × 0.005 + Albumin(g/dL) × 10), were evaluated as surrogate markers for underlying patient conditions. A total of 51 (19%) patients developed HCC recurrence. The use of sirolimus and sorafenib significantly improved outcome (p = 0.007 and 0.04), and better nutritional status (PNI ≥ 40) enhanced their efficacy. On multivariate analysis, low ALC (<500/μL) and albumin (<2.8 g/L) remained independent prognostic factors (p = 0.03 and 0.02; hazard ratio = 3.61 [Ref. >1000/μL] and 4.97 [Ref. >3.5 g/dL], respectively). Low PNI (<40) showed significantly lower survival rate after adjusting the risk (p = 0.006, hazard ratio = 3.29). Underlying patient conditions and nutritional status, represented by ALC and albumin, are important to successful cancer treatment and strong prognostic markers for survival after HCC recurrence.