Hepatocellular carcinoma (HCC) has high recurrence rates exceeding 50% despite curative resection. The serum biomarker alpha-fetoprotein (AFP) is a well-known prognostic marker for HCC. EpCAM-positive circulating tumor cells (CTC) have a high predictive value for early HCC recurrence after curatively intended resection, most likely indicating micro-metastases at the time of resection. However, sensitivity remains low. The objective of this study was to evaluate a composite test comprising both CTC and AFP to identify patients at high risk for early HCC recurrence. We prospectively enrolled 58 patients undergoing curative intended resection for HCC at a tertiary referral center. Blood specimens were obtained prior to resection and analyzed for EpCAM-positive CTC and serum AFP levels. A positive result was defined as either detection of CTC or AFP levels ≥ 400 ng/ml. Eight patients tested positive for CTC, seven for AFP, and two for both markers. A positive composite test was significantly associated with shorter early recurrence-free survival (5 vs. 16 months, p = 0.005), time to recurrence (5 vs. 16 months, p = 0.011), and overall survival (37 vs. not reached, p = 0.034). Combining CTC and AFP identified patients with poor outcome after surgical resection, for whom adjuvant or neoadjuvant therapies may be particularly desirable.