Relapse of adenocarcinoma, the most common non-small cell lung cancer (NSCLC), is a major clinical challenge to improving survival. To gain insight into the early molecular events that contribute to lung adenocarcinoma relapse, and taking into consideration potential cell type specificity, we used stringent criteria for sample selection. We measured miRNA expression only from flash frozen stage I lung adenocarcinomas, excluding other NSCLC subtypes. We compared miRNA expression in lung adenocarcinomas that relapsed within two years to those that did not relapse within three years after surgical resection prior to adjuvant therapy. The most significant differences in mRNA expression for recurrent tumors compared to non-recurrent tumors were decreases in miR-106b*, -187, -205, -449b, -774* and increases in miR-151-3p, let-7b, miR-215, -520b, and -512-3p. A unique comparison between adjacent normal lung tissue from relapse and non-relapse groups revealed dramatically different miRNA expression, suggesting dysregulation of miRNA in the environment around the tumor. To assess patient-to-patient variability, miRNA levels in the tumors were normalized to levels in matched adjacent normal lung tissue. This analysis revealed a different set of significantly altered miRNA in tumors that recurred compared to tumors that did not. Together our analyses elucidated miRNA not previously linked to lung adenocarcinoma that likely have important roles in its development and progression. Our results also highlight the differences in miRNA expression in normal lung tissue in adenocarcinomas that do and do not recur. Most notably, our data identified those miRNA that distinguish early stage tumors likely to relapse prior to treatment and miRNA that could be further studied for use as biomarkers for prognosis, patient monitoring, and/or treatment decisions.