Prostate cancer is the most common non-cutaneous malignancy in American men. Standard therapeutic strategies for systemic disease include androgen-deprivation therapy (ADT) and chemotherapy, both of which are palliative. However, there is a growing interest in the use of immunotherapy for prostate cancer. Evidence suggests that ADT may 1) enhance lymphopoiesis and thus potentially improve immune responses to vaccine, 2) renew thymopoiesis and thus reverse age-induced thymic involution, 3) augment B-cell development, and 4) mitigate tolerance to prostate cancer antigens. Although no vaccines are currently approved for prostate cancer, there are many promising agents under investigation. This review focuses on recent findings on immune regulation by androgens and immune-system regeneration with ADT, with emphasis on the rationale for the combination of ADT and vaccines in the clinical treatment of prostate cancer.