Docetaxel has activity against androgen-independent prostate cancer and preclinical studies have shown that taxane-based chemotherapy can enhance antitumor response of vaccines. The primary objective of this study was to determine if concurrent docetaxel (with dexamethasone) had any effect on generating an immune response to the vaccine. Secondary end points were whether vaccine could be given safely with docetaxel and the clinical outcome of the treatment regimen. The vaccination regimen was composed of (a) recombinant vaccinia virus (rV) that expresses the prostate-specific antigen gene (rV-PSA) admixed with (b) rV that expresses the B7.1 costimulatory gene (rV-B7.1), and (c) sequential booster vaccinations with recombinant fowlpox virus (rF-) containing the PSA gene (rF-PSA). Patients received granulocyte macrophage colony-stimulating factor with each vaccination. Twenty-eight patients with metastatic androgen-independent prostate cancer were randomized to receive either vaccine and weekly docetaxel or vaccine alone. Patients on the vaccine alone arm were allowed to cross over to receive docetaxel alone at time of disease progression. The ELISPOT assay was used to monitor immune responses for PSA-specific T cells. The median increase in these T-cell precursors to PSA was 3.33-fold in both arms following 3 months of therapy. In addition, immune responses to other prostate cancer-associated tumor antigens were also detected postvaccination. Eleven patients who progressed on vaccine alone crossed over to receive docetaxel at time of progression. Median progression-free survival on docetaxel was 6.1 months after receiving vaccine compared with 3.7 months with the same regimen in a historical control. This is the first clinical trial to show that docetaxel can be administered safely with immunotherapy without inhibiting vaccine specific T-cell responses. Furthermore, patients previously vaccinated with an anticancer vaccine may respond longer to docetaxel compared with a historical control of patients receiving docetaxel alone. Larger prospective clinical studies will be required to validate these findings.