Cervical cancer (CC) patients have a poor prognosis due to the high recurrence rate. However, there are still no effective molecular signatures to predict the recurrence and survival rates for CC patients. Here, we aimed to identify a novel signature based on three types of RNAs [messenger RNA (mRNAs), microRNA (miRNAs), and long non-coding RNAs (lncRNAs)]. A total of 763 differentially expressed mRNAs (DEMs), 46 lncRNAs (DELs), and 22 miRNAs (DEMis) were identified between recurrent and non-recurrent CC patients using the datasets collected from the Gene Expression Omnibus (GSE44001; training) and The Cancer Genome Atlas (RNA- and miRNA-sequencing; testing) databases. A competing endogenous RNA network was constructed based on 23 DELs, 15 DEMis, and 426 DEMs, in which 15 DELs, 13 DEMis, and 390 DEMs were significantly associated with disease-free survival (DFS). A prognostic signature, containing two DELs (CD27-AS1, LINC00683), three DEMis (hsa-miR-146b, hsa-miR-1238, hsa-miR-4648), and seven DEMs (ARMC7, ATRX, FBLN5, GHR, MYLIP, OXCT1, RAB39A), was developed after LASSO analysis. The built risk score could effectively separate the recurrence rate and DFS of patients in the high- and low-risk groups. The accuracy of this risk score model for DFS prediction was better than that of the FIGO (International Federation of Gynecology and Obstetrics) staging (the area under receiver operating characteristic curve: training, 0.954 vs 0.501; testing, 0.882 vs 0.656; and C-index: training, 0.855 vs 0.539; testing, 0.711 vs 0.508). In conclusion, the high predictive accuracy of our signature for DFS indicated its potential clinical application value for CC patients.