The tumor suppressor p53 is a central regulator of signaling pathways that controls the cell cycle and maintains the integrity of the human genome. p53 level is regulated by mouse double minute 2 homolog (Mdm2), which marks p53 for proteasomal degradation. The p53-Mdm2 circuitry is subjected to complex regulation by a variety of mechanisms, including microRNAs (miRNAs). We found a novel effector of this regulatory circuit, namely, miR-122*, the passenger strand of the abundantly expressed liver-specific miR-122. Here, we demonstrate that miR-122* levels are reduced in human hepatocellular carcinoma (HCC). We found that miR-122* targets Mdm2, thus participating as an important player in the p53-Mdm2 circuitry. Moreover, we observed significant negative correlation between levels of miR-122* and Mdm2 in a large set of human HCC samples. In vivo tumorigenicity assays demonstrate that miR-122* is capable of inhibiting tumor growth, emphasizing the tumor-suppressor characteristics of this miRNA. Furthermore, we show that blocking miR-122 in murine livers with an antagomiR-122 (miRNA inhibitor) results in miR-122* accumulation, leading to Mdm2 repression followed by elevated p53 protein levels.