Non-small cell lung cancer (NSCLC) constitutes approximately 80% of all diagnosed lung cancers and diagnostic markers detectable in the plasma/serum of NSCLC patients are greatly needed. Omic-based platforms have been promoted for the discovery of disease biomarkers. In this study, we established a pipeline for the discovery of markers using 10 transcriptome data sets obtained from the Gene Expression Omnibus (GEO) and the profiling of six lung cancer cell secretomes. Seventeen out of 281 proteins that overlapped between ±15% differentially expressed genes and identified cell secretome proteins were detected in the pooled plasma of lung cancer patients. In the verification process, 58 signature peptides for 17 candidates were first confirmed by Qtrap5500. To quantify the candidates in the serum of NSCLC patients, multiple reaction monitoring mass spectrometry (MRM-MS) with stable isotope-labeled standard (SIS) peptides was performed for eight candidate biomarkers. Finally, two potential biomarkers (BCHE and GPX3; AUC = 0.918 and 0.728, respectively) and one two-marker panel (BCHE/GPX3; AUC = 0.943) were able to effectively differentiate NSCLC from healthy controls. Collectively, these results demonstrate that our pipeline for marker discovery and our MRM-MS platform for verifying potential biomarkers are feasible for use with human diseases.