Tremendous efforts have been made to develop cancer biomarkers by detecting circulating extracellular miRNAs directly released from tumors. Yet, none of the cell-free biomarkers has been accepted to be used for early detection of non-small cell lung cancer (NSCLC). Peripheral blood mononucleated cells (PBMCs) act as the first line of defense against malignancy in immune system, their dysfunction may occur as an early event in cancer immunogenicity or immune evasion. We proposed to investigate whether analysis of miRNA expressions of PBMCs has diagnostic value for NSCLC. We first used a microarray to analyze PBMCs of 16 stage I NSCLC patients and 16 cancer-free smokers, and identified seven PBMC miRNAs with a significantly altered expression level in NSCLC patients. In a training set of 84 NSCLC patients and 69 cancer-free smokers, a panel of two miRNAs (miRs-19b-3p and -29b-3p) were developed from the seven PBMC miRNAs, producing 72.62% sensitivity and 82.61% specificity in identifying NSCLC. Furthermore, the miRNAs could identify squamous cell lung carcinoma (SCC), a major type of NSCLC, with 80.00% sensitivity and 89.86% specificity. The expression levels of the miRNAs were independent of disease stage. In a testing set of 56 NSCLC patients and 46 controls, the performance of the biomarkers was reproducibly confirmed. The study presents the first in-depth analysis of PBMC miRNA profile of NSCLC patients. The assessment of PBMC miRNAs may provide a new diagnostic approach for the early detection of NSCLC.