The high morbidity rate of hepatocellular carcinoma (HCC) is mainly linked to late diagnosis. Early diagnosis of this leading cause of mortality is therefore extremely important. We designed a gene selection strategy to identify potential secretory proteins by predicting signal peptide cleavage sites in amino acid sequences derived from transcriptome data of human multistage HCC comprising chronic hepatitis, liver cirrhosis and early and overt HCCs. The gene selection process was validated by the detection of molecules in the serum of HCC patients. From the computational approaches, 10 gene elements were suggested as potent candidate secretory markers for detecting HCC patients. ELISA testing of serum showed that hyaluronan mediated motility receptor (HMMR), neurexophilin 4 (NXPH4), paired like homeodomain 1 (PITX1) and thrombospondin 4 (THBS4) are early-stage HCC diagnostic markers with superior predictive capability in a large cohort of HCC patients. In the assessment of differential diagnostic accuracy, receiver operating characteristic curve analyses showed that HMMR and THBS4 were superior to alpha-fetoprotein (AFP) in diagnosing HCC, as evidenced by the high area under the curve, sensitivity, specificity, accuracy and other values. In addition, comparative analysis of all four markers and AFP combinations demonstrated that HMMR-PITX1-AFP and HMMR-NXPH4-PITX1 trios were the optimal combinations for reaching 100% accuracy in HCC diagnosis. Serum proteins HMMR, NXPH4, PITX1 and THBS4 can complement measurement of AFP in diagnosing HCC and improve identification of patients with AFP-negative HCC as well as discriminate HCC from non-malignant chronic liver disease.