Loss of olfactomedin 4 (OLFM4) gene expression is associated with the progression of human prostate cancer, but its role and the molecular mechanisms involved in this process have not been completely understood. In this study, we found that Olfm4-knockout mice developed prostatic intraepithelial neoplasia and prostatic adenocarcinoma. Importantly, we found that the hedgehog-signaling pathway was significantly upregulated in the Olfm4-knockout mouse model. We also found that restoration of OLFM4 in human prostate-cancer cells that lack OLFM4 expression significantly downregulated hedgehog signaling-pathway component expression. Furthermore, we demonstrated that the OLFM4 protein interacts with sonic hedgehog protein, as well as significantly inhibits GLI-reporter activity. Bioinformatic and immunohistochemistry analyses revealed that decreased OLFM4 and increased SHH expression was significantly associated with advanced human prostate cancer. Thus, olfactomedin 4 appears to play a critical role in regulating progression of prostate cancer, and has potential as a new biomarker for prostate cancer.