Background: We have previously demonstrated potent immunogenicity of the NY-ESO-1/ISCOMATRIX vaccine in patients with resected melanoma; however the same vaccine induced only a few vaccine antigen specific immune responses in patients with advanced disease. Therefore, we have enrolled a second cohort of patients with advanced melanoma in the clinical trial LUD2002-013 to investigate whether pre-treatment with the immune-modulator cyclophosphamide could improve the immunogenicity of the NY-ESO-1/ISCOMATRIX vaccine. Methods: LUD2002-013 was an open-label phase II study intended to evaluate the safety and immunogenicity of the NY-ESO-1/ISCOMATRIX vaccine in patients with advanced melanoma. The first cohort of patients received vaccine alone; a second cohort with 19 patients was added after evaluation of responses in Cohort 1 and received vaccine in combination with low-dose cyclophosphamide. Patients received 3 injections of NY-ESO-1 ISCOMATRIX preceded, in Cohort 2, by cyclophosphamide at a dose of 300 mg/m² every four weeks. Assessment of clinical and immunological responses was undertaken at week 11. Results: Fifteen patients of Cohort 2 completed at least one cycle of vaccination. No objective responses were observed with three patients having stable disease for more than three months. The inclusion of cyclophosphamide into the vaccination protocol did not lead to any significant toxicity. Seven of fourteen patients in Cohort 2 developed a vaccine induced NY-ESO-1 specific CD4 T cell response, a significant increase compared to cohort 1 (p=0.019). No differences were observed in the frequency of vaccine induced antibody or CD8 T cell responses. No change in the frequency of peripheral blood regulatory T cells or myeloid derived suppressor cells was detected. Conclusions: The administration of low dose cyclophosphamide has significantly increased the NY-ESO-1 specific CD4 T cell response of the NY-ESO-1/ISCOMATRIX vaccine in patients with metastatic melanoma. Given the emerging importance of CD4 T cells in tumour regression, the present findings warrant further clinical exploration of combining cyclophosphamide with vaccines and other immune-modulatory agents. Clinical trial information: NCT00518206.