The recent advancements in proteomic technologies have reconstituted our research strategies over different type of liver diseases including hepatocellular carcinoma (HCC). Combined analyses on HCC proteome and clinicopathological data of patients have allowed identification of many promising biomarkers that can be further developed into noninvasive diagnostic assays for cancer surveillance. Capitalizing our established proteomic platform primarily based on two-dimensional polyacrylamide gel electrophoresis (2DE) and MALDI-TOF/TOF mass spectrometry, our groups have identified lamin B1 (LMNB1) and vimentin (VIM) as promising biomarkers for detection of early HCC. Protein levels of both biomarkers were significantly elevated in cancerous tissues when compared to the controls in disease-free and cirrhotic liver subjects. Further investigation of the circulating LMNB1 mRNA level in patients' blood samples by standard PCR showed 76% sensitivity and 82% specificity for detection of early HCC. In parallel, an ELISA assay for measuring circulating vimentin level in patients' serum samples could detect small HCC at 40.91% sensitivity and 87.5% specificity. The candidate biomarkers were evaluated with the diagnostic performance of α-fetoprotein (AFP) for HCC. In this article, we address the current protocols for HCC biomarker discovery, ranging from clinical sample preparation, 2DE proteomic profiling and informatics analysis, and assay development and clinical validation study. Focus is emphasized on the methods for sample preservation and low-abundance protein enrichment.