The objective of this research is to use metabolomic techniques to discover and validate plasma metabolite biomarkers for the diagnosis of early-stage non-small cell lung cancer (NSCLC). The study included plasma samples from 156 patients with biopsy-confirmed NSCLC along with age and gender-matched plasma samples from 60 healthy controls. A fully quantitative targeted mass spectrometry (MS) analysis (targeting 138 metabolites) was performed on all samples. The sample set was split into a discovery set and validation set. Metabolite concentration data, clinical data, and smoking history were used to determine optimal sets of biomarkers and optimal regression models for identifying different stages of NSCLC using the discovery sets. The same biomarkers and regression models were used and assessed on the validation models. Univariate and multivariate statistical analysis identified β-hydroxybutyric acid, LysoPC 20:3, PC ae C40:6, citric acid, and fumaric acid as being significantly different between healthy controls and stage I/II NSCLC. Robust predictive models with areas under the curve (AUC) > 0.9 were developed and validated using these metabolites and other, easily measured clinical data for detecting different stages of NSCLC. This study successfully identified and validated a simple, high-performing, metabolite-based test for detecting early stage (I/II) NSCLC patients in plasma. While promising, further validation on larger and more diverse cohorts is still required.