Renal cell carcinoma (RCC) is the most common neoplasm of adult kidney. One of the important unmet medical needs in RCC is prognostic biomarker enabling identification of patients at high risk of relapse after nephrectomy. MicroRNAs (miRNAs) constitute a robust regulatory network with posttranscriptional regulatory efficiency for almost one-half of human coding genes, including oncogenes and tumor suppressors. To identify potential prognostic miRNAs, we analyzed expression profiles in tumors of different prognostic groups of RCC patients. Seventy-seven patients with clear cell RCC and detailed clinicopathological data were enrolled in a single-center study. Global miRNA expression profiles were obtained by use of TaqMan Low Density Arrays (754 parallel quantitative reverse-transcriptase polymerase chain reactions (qRT-PCR) reactions). For validation of identified miRNAs individual miRNA TaqMan assays were performed in an independent group of patients. We identified tumor relapse-signature based on the expression of 64 miRNAs differentially expressed between relapse-free RCC patients and RCC patients who developed relapse (20 miRNAs were increased, 44 miRNAs were decreased). In the validation phase of the study, we successfully confirmed that expression levels of miR-143, miR-26a, miR-145, miR-10b, miR-195, and miR-126 are lower in the tumors of RCC patients who developed tumor relapse, moreover, the lowest levels of these miRNAs we observed in primary metastatic tumors. By using Kaplan-Meier analysis, we identified that miR-127-3p, miR-145, and miR-126 are significantly correlated with relapse-free survival of nonmetastatic RCC patients. If further validated, we suggest that identified miRNAs might be used for identification of RCC patients at high risk of early relapse after nephrectomy in clinical practice.