MicroRNAs (miRNAs) play an important role in carcinogenesis through the regulation of their target genes. miRNA-related single nucleotide polymorphisms (miR-SNPs) can affect miRNA biogenesis and target sites and can alter microRNA expression and functions. We examined 11 miR-SNPs, including 5 in microRNA genes, 3 in microRNA binding sites and 3 in microRNA-processing machinery components, and evaluated time to recurrence (TTR) according to miR-SNP genotypes in 175 surgically resected non-small-cell lung cancer (NSCLC) patients. Significant differences in TTR were found according to KRT81 rs3660 (median TTR: 20.3 months for the CC genotype versus 86.8 months for the CG or GG genotype; P = 0.003) and XPO5 rs11077 (median TTR: 24.7 months for the AA genotype versus 73.1 months for the AC or CC genotypes; P = 0.029). Moreover, when patients were divided according to stage, these differences were maintained for stage I patients (P = 0.002 for KRT81 rs3660; P<0.001 for XPO5 rs11077). When patients were divided into sub-groups according to histology, the effect of the KRT81 rs3660 genotype on TTR was significant in patients with squamous cell carcinoma (P = 0.004) but not in those with adenocarcinoma. In the multivariate analyses, the KRT81 rs3660 CC genotype (OR = 1.8; P = 0.023) and the XPO5 rs11077 AA genotype (OR = 1.77; P = 0.026) emerged as independent variables influencing TTR. Immunohistochemical analyses in 80 lung specimens showed that 95% of squamous cell carcinomas were positive for KRT81, compared to only 19% of adenocarcinomas (P<0.0001). In conclusion, miR-SNPs are a novel class of SNPs that can add useful prognostic information on the clinical outcome of resected NSCLC patients and may be a potential key tool for selecting high-risk stage I patients. Moreover, KRT81 has emerged as a promising immunohistochemical marker for the identification of squamous cell lung carcinoma.