The ability to diagnose non-small cell lung cancer (NSCLC) at an early stage may lead to improved survival. The aim of this study was to identify differentially expressed serum-based microRNAs (miRNAs) between patients with early-stage NSCLC and controls. These miRNAs may serve as biomarkers for NSCLC early detection. miRNA profiling was performed on total RNA extracted from serum obtained from 22 individuals (11 controls and 11 patients with early-stage NSCLC). Quantitative polymerase chain reaction (qPCR) was used to validate the profiling results in the discovery set and in a validation set of 31 controls and 22 patients with early-stage NSCLC. Additionally, six matched plasma samples (four NSCLC cases and two controls) and three serum mesothelioma samples were analyzed by qPCR. Receiver operating characteristic curves were generated for each possible combination of the miRNAs measured by qPCR. The expression of hsa-miR-1254 and hsa-miR-574-5p was significantly increased in the early-stage NSCLC samples with respect to the controls. Receiver operating characteristic curves plotting these two miRNAs were able to discriminate early-stage NSCLC samples from controls with 82% and 77% of sensitivity and specificity, respectively, in the discovery cohort and with 73% and 71% of sensitivity and specificity, respectively, in the validation cohort. The mesothelioma and plasma samples did not seem to classify into either NSCLC or control groups. Serum miRNAs are differentially expressed between patients with early-stage NSCLC and controls. The utility of miR-1254 and miR-574-5p serum-based biomarkers as minimally invasive screening and triage tools for subsequent diagnostic evaluation warrants additional validation.