Prognostic markers that can predict the relapse of localized non–small cell lung cancer (NSCLC) have yet to be defined. We surveyed expression profiles of microRNA (miRNA) in stage I NSCLC to identify patterns that might predict recurrence after surgical resection of this common deadly cancer. Small RNAs extracted from formalin-fixed and paraffin-embedded tissues were hybridized to locked nucleic acid probes against 752 human miRNAs (representing 82% of the miRNAs in the miRBase 13.0 database) to obtain expression profiles for 37 cases with recurrence and 40 cases without recurrence (with clinical follow-up for at least 32 months). Differential expression between the two case groups was detected for 49% of the miRNAs (Wilcoxon rank sum test; P < 0.01). The performance of expression profiles at differentiating the two case groups was assessed by leave-one-out and Monte Carlo cross-validations. In leave-one-out cross-validation using support vector machines- or top-scoring gene pair classifier methods, which looked for six- or two-miRNA-based classifiers, the identified miRNA expression pattern predicted recurrence with an accuracy of 70% and 83%, and hazard ratio of 3.6 [95% confidence interval (95% CI), 1.8–7.1] and 9.0 (95% CI, 4.4–18.2), respectively. Mean accuracy in Monte Carlo cross-validation using 1,000 random 60–17 splits was 69% (95% CI, 68–70) and 72% (95% CI, 71–72), respectively. The specific miRNAs mir-200b*, mir-30c-1*, mir-510, mir-630, mir-657, and mir-146b-3p and mir-124*, mir-585, and mir-708, respectively, represented most commonly among the 1,000 classifiers identified in Monte Carlo cross-validation by the two methods. MiRNAs mir-488, mir-503, and mir-647 were identified as potential reference miRNAs for future studies, based on the stability of their expression patterns across the 77 cases and the two case-groups. Our findings reinforce efforts to profile miRNA expression patterns for better prognostication of stage I NSCLC. Cancer Res; 70(1); 36–45