Purpose The combination of gemcitabine plus cisplatin (GC) is a standard regimen in patients with locally advanced or metastatic urothelial cancer. A phase I/II study suggested that a three-drug regimen that included paclitaxel had greater antitumor activity and might improve survival. Patients and Methods We conducted a randomized phase III study to compare paclitaxel/cisplatin/gemcitabine (PCG) with GC in patients with locally advanced or metastatic urothelial carcinoma. Primary outcome was overall survival (OS). Secondary outcomes were progression-free survival (PFS), overall response rate, and toxicity. Results From 2001 to 2004, 626 patients were randomly assigned; 312 patients were assigned to PCG, and 314 patients were assigned to GC. After a median follow-up of 4.6 years, the median OS was 15.8 months on PCG versus 12.7 months on GC (hazard ratio [HR], 0.85; P = .075). OS in the subgroup of all eligible patients was significantly longer on PCG (3.2 months; HR, 0.82; P = .03), as was the case in patients with bladder primary tumors. PFS was not significantly longer on PCG (HR, 0.87; P = .11) Conclusion The addition of paclitaxel to GC provides a higher response rate and a 3.1-month survival benefit that did not reach statistical significance. Novel approaches will be required to obtain major improvements in survival of incurable urothelial cancer.