Micro RNAs (miRNA) are small non-coding RNAs that post-transcriptionally regulate gene expression. Dysregulation of miRNA cluster 143/145 has been reported in several malignancies, but their role in non-small cell lung cancer (NSCLC) remains elusive. This study investigates the prognostic impact of miR-143 and miR-145 in primary tumors and metastatic lymph nodes in NSCLC tissue. Tissue from 553 primary tumors and 143 matched metastatic lymph nodes were collected and tissue microarrays were constructed. In situ hybridization was used to evaluate miR-143 and miR-145 expression in tumor epithelial cells and stromal cells in the primary tumors and lymph nodes. In vivo data was supplemented with functional studies of cell lines in vitro to evaluate the role of miR-143 and miR-145 in NSCLC tumorigenesis. In our cohort, stromal miR-143 (S-miR-143) and miR-145 (S-miR-145) expression in primary tumor tissue were independent prognosticators of improved disease-specific survival (DSS) in female (S-miR-143, HR: 0.53, p = 0.019) and male patients (S-miR-145, HR: 0.58, p = 0.021), respectively. Interesting correlations between the miR cluster 143/145 and previously investigated steroid hormone receptors from the same cohort were identified, substantiating their gender dependent significance.