Inclusion Criteria:

- Histologic proof of adenocarcinoma of the prostate.

- Patients must belong to one of four groups: 1) Local/Regional with prior definitive
therapy: Patients with local/regional recurrence following prostatectomy or radiation
therapy who still have a normal bone scan. 2) Local/Regional without prior definitive
therapy: Patients felt to be unresectable, or are felt not to be candidates for,
radiation therapy. 3) Low volume bone disease: Patients with 1 or 2 bone metastases.
4) High volume bone/visceral disease: Patients with ≥ 3 metastatic bone sites or
visceral metastases.

- Patients meeting these criteria are eligible even without any radiographically
demonstrable abnormality. All patients must have an elevated PSA prior to initial
hormone exposure defined as: 1) For patients with prior prostatectomy, the PSA must
be rising with an associated doubling time of ≤ 3 months. 2) For patients with prior
radiation therapy, the PSA must be ≥ 1.0 ng/mL with an associated doubling time of ≤
3 months. 3) For patients with the prostate in place, the PSA must be elevated with
biopsy proven disease and are not candidates for local therapy.

- Patients may be on an LHRH agonist (with or without an anti-androgen), or already
medically castrated, at the time of study entry, provided such therapy was started
within 3 months of study entry.

- No previous cytotoxic systemic therapy of any kind is allowed, including systemic
irradiation with strontium-89 and samarium. Previous definitive radiotherapy to one
metastatic site is acceptable. At least 8 weeks must have elapsed since radiation
therapy to the pelvis. Patients having limited irradiation of a single metastatic
site are eligible 4 weeks following the completion of radiation.

- Patients may have had previous exposure to androgen deprivation therapy if it was
given for ≤ 6 months to, "downstage" the primary, and provided such therapy completed
at least 12 months prior to entry into this study.

- Patients must be free of serious co-morbidity and have a life expectancy of ≥ 3
years.

- Patients must have adequate physiologic reserves as evidenced by Zubrod Performance
Status (ZPS) of ≤ 2, adequate bone marrow function, renal function and liver function
and no evidence of active ischemia on ECG (if clinically indicated, documentation of
EF ≥ 40%.)

Exclusion Criteria:

- Patients must not have a second malignancy unless there is confidence of previous
curative therapy.

- Patients with a recent history of TIA (within 6 months), or are requiring regular
antianginal therapy or are having claudication sufficient to limit activity are not
eligible. Patients with a previous history of deep venous thrombosis or pulmonary
embolism (within 12 months) are not eligible.

- Patients must not have a serious intercurrent medical or psychiatric illness,
including serious active infection.

- Patients must not have Sensory neuropathy of grade 1 or greater.