Purpose: To compare vinblastine versus the combination of vinblastine plus estramustine as treatment for patients with hormone-refractory prostate cancer (HRPC). Patients and Methods: A total of 201 patients with metastatic prostate cancer, progressive after hormonal therapy and antiandrogen withdrawal (if prior antiandrogen treatment), were randomized to receive vinblastine (V) 4 mg/m2 by intravenous bolus weekly for 6 weeks followed by 2 weeks off, either alone or together with estramustine phosphate (EM-V) 600 mg/m2 PO days 1 through 42, repeated every 8 weeks. Of 193 eligible patients, 98 received V, and 95 received EM-V. Results: Overall survival trended in favor of EM-V but was not significantly different as determined by Kaplan-Meier analysis (P = .08). Median survival was 11.9 months for EM-V and 9.2 months for V. EM-V was superior to V for secondary end points of time to progression (P < .001, stratified log rank test; median 3.7 v 2.2 months, respectively) and for proportion of patients with ≥ 50% prostate-specific antigen (PSA) decline sustained for at least 3 monthly measurements (25.2% v 3.2%, respectively; P < .0001). Granulocytopenia was significantly less for EM-V compared with V (grade 2, 3, and 4 = 7%, 7%, and 1% v 27%, 18% and 9%, respectively; P < .0001); however, grade 2 or worse nausea (26% v 7%, respectively; P = .0002) and extremity edema (22% v 8%, respectively; P = .005) were more frequent for EM-V. Conclusion: Although overall survival was not significantly greater for the combination, EM-V was superior to V for time to progression and PSA improvement. These results encourage further study of estramustine-based antimicrotubule drug combinations in HRPC.