The application of non-targeted serum metabolomics profiling represents a noninvasive tool to identify new clinical biomarkers and to provide early diagnostic differentiation, and insight into the pathological mechanisms underlying hepatocellular carcinoma (HCC) progression. In this study, we used proton Nuclear Magnetic Resonance (H-NMR) Spectroscopy and multivariate data analysis to profile the serum metabolome of 64 HCC patients, in early (n = 28) and advanced (n = 36) disease stages. We found that H-NMR metabolomics profiling could discriminate early from advanced HCC patients with a cross-validated accuracy close to 100%. Orthogonal partial least squares discriminant analysis (OPLS-DA) showed significant changes in serum glucose, lactate, lipids and some amino acids, such as alanine, glutamine, 1-methylhistidine, lysine and valine levels between advanced and early HCC patients. Moreover, in early HCC patients, Kaplan-Meier analysis highlighted the serum tyrosine level as a predictor for overall survival (OS). Overall, our analysis identified a set of metabolites with possible clinical and biological implication in HCC pathophysiology.