Nm23-H1 has been identified as a metastatic suppressor gene in murine melanoma cell lines. Several functions have been attributed to its activity in cancer, including a histidine kinase activity, DNA repair, and regulation of other proteins involved in metastatic formation. While in breast cancer, NM23-H1 overexpression indicates a benign status through impairing progression of disease, its function is opposite in other cancers; e.g., neuroblastoma. To further understand this dichotomy of function in cancer, we have analyzed its function in prostate cancer, in which the relationship between NM23-H1 expression and prognostic state is today controversial. In vitro, overexpression of NM23-H1 in PC3 cells inhibited their cell motility, while downregulation of NM23-H1 expression in these cells by RNA interference showed enhanced cell motility. Immunohistochemistry analysis performed on 346 prostate cancer tissue samples showed a relationship between high levels of NM23-H1 expression in the nuclei of these tumorigenic cells and elevated Gleason score, with high levels of NM23-H1 cytoplasmic staining related to metastatic stage. This retrospective survival study demonstrates that high levels of NM23-H1 expression in the cytoplasm determine recurrence of prostate-specific antigen levels only in those patients with metastatic disease. Our findings suggest a correlation between high levels of NM23-H1 protein in the cytoplasm of the cells and progression of prostate cancer to metastasis, thus definitively identifying NM23-H1 as a new negative prognostic marker in prostate cancer.