Inclusion Criteria:

          -  Histologically confirmed adenocarcinoma of the prostate

          -  Recurrent prostate cancer following primary therapy as defined by:

               -  Post-radical prostatectomy: Any PSA >= 0.4 ng/ml

               -  Post-primary radiotherapy: PSA >= 2 ng/ml above a post-radiotherapy nadir

               -  Post-primary androgen-deprivation therapy: A confirmed rise of PSA >= 2 ng/ml
                  above a post-therapy nadir

          -  For patients with non-castrate levels of circulating androgen levels (testosterone >=
             50 g/dl)

               -  PSA levels should be increasing on at least two occasions >= 1 week apart

               -  Patients should not be considered candidates for radiation therapy

          -  For patients with castrate levels of circulating androgen levels (testosterone < 50
             ng/dl):

               -  PSA levels must be >= 0.4 ng/ml (if history of radical prostatectomy) or >= 2
                  ng/ml (if history of non-surgical primary treatment) and found to be increasing
                  on at least two occasions >= 1 week apart

          -  At least 4 weeks must have elapsed since any changes to hormonal therapy, including at
             least 4 weeks since flutamide and at least 6 weeks since bicalutamide, nilutamide, or
             enzalutamide

          -  No evidence of metastatic cancer on imaging including a bone scan and computed
             tomography (CT) scan of chest/abdomen/pelvis

          -  Able to understand and adhere to dietary and medication restrictions as recommended
             for the safe use of phenelzine

          -  Men with child bearing potential are required to use an effective means of
             contraception

          -  Leukocytes >= 3,000/mcL

          -  Absolute neutrophil count >= 1,500/mcL

          -  Platelets >= 100,000/mcL

          -  Total bilirubin =< 1.5 x upper limit of normal (ULN) except in cases of benign
             isolated hyperbilirubinemia such as Gilbert's syndrome.

          -  Aspartate aminotransferase (AST) (serum glutamic oxaloacetic transaminase
             [SGOT])/alanine aminotransferase (ALT) (serum glutamate pyruvate transaminase [SPGT])
             =< 2.5 x ULN

          -  Creatinine =< 1.5 x ULN

        Exclusion Criteria:

          -  Uncontrolled hypertension despite appropriate medical therapy (blood pressure [BP]
             greater than 160 mmHg systolic and 90 mmHg diastolic at 2 separate measurements no
             more than 60 minutes apart during the screening visit); Note: patients may be
             rescreened after adjustment of antihypertensive medications

          -  Known prior history of mania or major psychiatric illness (schizophrenia, bipolar
             disorder, severe major depression requiring hospitalization, etc.)

          -  Concurrent use of medications contra-indicated due to potential interactions with
             phenelzine

          -  Inability to comply with dietary restrictions for foods, supplements, and medications
             with potential for adverse interactions with phenelzine or to otherwise cooperate
             fully with the investigator and study personnel

          -  History of allergic reactions attributed to compounds of similar chemical or biologic
             composition to phenelzine or other monoamine oxidase inhibitors

          -  Patients may not be receiving any other investigational agents

          -  Uncontrolled intercurrent illness including, but not limited to, ongoing or active
             infection, symptomatic congestive heart failure, unstable angina pectoris, cardiac
             arrhythmia, or psychiatric illness/social situations that would limit compliance with
             study requirements