Purpose Both docetaxel and thalidomide have demonstrated activity in androgen-independent prostate cancer (AIPC). We compared the efficacy of docetaxel to docetaxel plus thalidomide in patients with AIPC. Methods Seventy-five patients with chemotherapy-naive metastatic AIPC were randomly assigned to receive either docetaxel 30 mg/m2 intravenously every week for 3 consecutive weeks, followed by a 1-week rest period (n = 25); or docetaxel at the same dose and schedule, plus thalidomide 200 mg orally each day (n = 50). Prostate-specific antigen (PSA) consensus criteria and radiographic scans were used to determine the proportion of patients with a PSA decline, and time to progression. Results After a median potential follow-up time of 26.4 months, the proportion of patients with a greater than 50% decline in PSA was higher in the docetaxel/thalidomide group (53% in the combined group, 37% in docetaxel-alone arm). The median progression-free survival in the docetaxel group was 3.7 months and 5.9 months in the combined group (p = .32). At 18 months, overall survival in the docetaxel group was 42.9% and 68.2% in the combined group. Toxicities in both groups were manageable after administration of prophylactic low-molecular-weight heparin in the combination group. Conclusion In this randomized phase II trial, the addition of thalidomide to docetaxel resulted in an encouraging PSA decline rate and overall median survival rate in patients with metastatic AIPC. After the prophylactic low-molecular-weight heparin was instituted to prevent venous thromboses, the combination regimen was well tolerated. Larger randomized trials are warranted to assess the impact of this combination.