Hepatocellular carcinoma (HCC) is a malignant tumor with the fourth highest incidence and the third highest mortality among all tumor sites in China. Finding new diagnostic markers and therapeutic molecules may be of great value in the treatment of HCC and the improvement of prognosis. MicroRNA (miRNA) is a type of short, approximately 18~22 nucleotides (nt) long, single-stranded noncoding RNA. Increasing evidence indicates microRNAs are involved in various cellular and biological processes of HCC. However, a complete picture of the miRNA targetome, which defines the number of oncogenes or tumor suppressors targeted by a particular miRNA, has yet to be generated. To investigate novel differentially expressed miRNAs in HCC, we performed small RNA deep sequencing analysis in 15 liver tissue samples and validated a novel miRNA (tentatively named miR-MTCO3P38), which derived from 5′-end of the pseudogene MTCO3P38. MiR-MTCO3P38 was downregulated in HCC tissues and significantly related to the overall survival (OS) of HCC patients. Further study showed miRMTCO3P38 inhibits malignant progression via STAT3/PTTG1/MYC in hepatocellular carcinoma.