We report the case of a 47-year-old male patient who suffered from a malignant phyllodes tumor of the prostate with invasion to the rectum and urinary bladder. The local recurrence at the left scrotum was identified 6 years after radical cystoprostatectomy. Another 2 years after radical orchiectomy showed no evidence of secondary local recurrence or distant metastasis. Histopathologically, both primary and recurrent tumors showed an admixture of stromal and glandular components. However, while extensive squamous metaplasia was identified in the primary tumor, the recurrent tumor had only focal and mild squamous metaplasia. No dependable prognostic factor has been found to date. Here, we describe the morphological features and immunohistochemical presentations of malignant phyllodes tumor of the prostate and review the literature.