The abnormal expression of microRNAs (miRNAs) or protein-coding genes (PCGs) have been found to be associated with the prognosis of hepatocellular carcinoma (HCC) patients. Using bioinformatics analysis methods including Cox's proportional hazards regression analysis, the random survival forest algorithm, Kaplan-Meier, and receiver operating characteristic (ROC) curve analysis, we mined the gene expression profiles of 469 HCC patients from The Cancer Genome Atlas (n=379) and Gene Expression Omnibus (GSE14520; n=90) public database. We selected a signature comprising one protein-coding gene (PCG; DNA polymerase ) and three miRNAs (hsa-miR-149-5p, hsa-miR-424-5p, hsa-miR-579-5p) with highest accurate prediction (area under the ROC curve [AUC]=0.72; n=189) from the training data set. The signature stratified patients into high- and low-risk groups with significantly different survival (median 27.9 vs. 55.2 months, log-rank test, p<0.001) in the training data set, and its risk stratification ability were validated in the test data set (median 47.4 vs. 84.4 months, log-rank test, p=0.03) and an independent data set (median 31.0 vs. 46.0 months, log-rank test, p=0.01). Multivariable Cox regression analysis showed that the signature was an independent prognostic factor. And the signature was proved to have a better survival prediction power than tumor-node-metastasis (TNM) stage (AUC (signature)=0.72/0.64/0.62 vs. AUC (TNM)=0.65/0.61/0.61; p<0.05). Moreover, we validated the expression of these prognostic genes from the PCG-miRNA signature in Huh-7 cell by real-time polymerase chain reaction. In conclusion, we found a signature that can predict survival of HCC patients and serve as a prognostic marker for HCC.