Prostate cancer is responsible for the deaths of more than 33,000 American men every year. Once this disease has become metastatic, there is no curative treatment. Alternative therapies to chemotherapy and radical prostatectomy are being increasingly explored. Prostate cancer vaccines--which trigger a tumour-specific cytotoxic-T-lymphocyte-mediated immune attack by the patient's immune system--have been investigated in clinical trials with modest, yet encouraging, results. When developing and administering prostate cancer vaccines, it is critical to consider how vital parameters, such as the stage of disease progression and the nature of adjuvant therapies, could influence treatment outcome. Of particular interest are current and future strategies for diminishing the activity of regulatory T lymphocytes.