Clinical outcomes from cancer vaccine trials in patients with advanced melanoma have so far been disappointing. This appears at least partially due to a state of immunosuppression in these patients induced by an expansion of regulatory cell populations including regulatory T cells (Tregs). We have previously demonstrated potent immunogenicity of the NY-ESO-1/ISCOMATRIX™ vaccine in patients with resected melanoma (study LUD99-08); however, the same vaccine induced only a few vaccine antigen-specific immune responses in patients with advanced disease (study LUD2002-013). Pre-clinical models suggest that the alkylating agent cyclophosphamide can enhance immune responses by depleting Tregs. Therefore, we have enrolled a second cohort of patients with advanced melanoma in the clinical trial LUD2002-013 to investigate whether pre-treatment with cyclophosphamide could improve the immunogenicity of the NY-ESO-1/ISCOMATRIX™ vaccine. The combination treatment led to a significant increase in vaccine-induced NY-ESO-1-specific CD4(+) T cell responses compared with the first trial cohort treated with vaccine alone. We could not detect a significant decline in regulatory T cells in peripheral blood of patients 14 days after cyclophosphamide administration, although a decline at an earlier time point cannot be excluded. Our observations support the inclusion of cyclophosphamide in combination trials with vaccines and other immune-modulatory agents.