Hepatocellular carcinoma (HCC) is among the most aggressive and lethal human tumors. Many functional studies have demonstrated the role of non-coding RNAs (ncRNA), particularly microRNAs (miRNA), in the regulation of hepatocarcinogenesis driving pathways. MiR-125a-5p (miR-125a) has been consistently reported as an oncosuppressive miRNA, as demonstrated in vivo and in vitro. However, its HCC relevant targets and molecular mechanisms are still largely unknown. Here, a genome-wide perspective of the whole miR-125a targetome has been achieved. In particular, two different HCC cell lines were subjected to a miRNA boosting by mimic transfections, and consequently many genes were de-regulated, as observed by a transcriptomic approach. The merging of down-regulated genes with results from bioinformatic predictive tools yielded a number of candidate direct targets that were further experimentally validated by luciferase-based reporter assays. Different novel targets were found, in particular ARID3A, CCNJ, LIPA, NR6A1, and NUP210, oncogenes in various tumors and here also related to HCC through miR-125a regulation. The RNA interactions investigated in this work could pave the way to piece together the RNA regulatory networks governed by the miRNA impacting on hepatocarcinogenesis, and be exploited in the future for identifying novel biomarkers and therapeutic targets in HCC.