Objective Many studies have revealed the crucial roles of miRNA in multiple human cancers, including lung adenocarcinoma (LUAD). In this study, we sought to explore new miRNA-mRNA pairs that are associated with LUAD prognosis. Methods A novel miRNA-mRNA regulatory network associated with prognosis in LUAD was identified and validated using the bioinformatic tools including OncomiR database, StarBase, miRnet, GEPIA2, UALCAN. Results Twenty key miRNAs were compiled after the analysis of the expression and prognostic value in OncomiR and StarBase. Targeted mRNAs of these key miRNAs were predicted in miRnet, and the resulting mRNAs were also analyzed for their prognostic values and expression patterns in GEPIA2 and UALCAN, respectively. Further expression correlation analysis was performed in StarBase. Subsequently, a new miRNA-mRNA network was built, of which each RNA pair showed negative expression correlation, opposite expression pattern, and prognostic value. Protein-protein interaction network was under construction for the mRNAs, and 19 hub genes were determined. Enrichment analysis showed that "Cell Cycle, Mitotic" was the most significantly enriched term. Then, a miRNA-hub gene sub-network was built. We selected and validated the regulatory relationship of some miRNA-hub pairs, including hsa-miR-1976/RFC2, hsa-let-7c-5p/RFC2, hsa-let-7c-5p/ESPL1, hsa-let-7c-5p/CDC25A, and hsa-miR-101-3p/KIF2C. Moreover, over-expression of hsa-miR-1976 and hsa-let-7c-5p resulted in significant cell cycle arrest. Conclusions Our results determined new prognosis-associated miRNA-mRNA pairs and might shed further light on the mechanism via which miRNA-mRNA network influences prognosis in LUAD.