Dendritic cells (DC) are the most potent antigen presenting cells and have proven effective in stimulation of specific immune responses in vivo. Competing immune inhibition could limit the clinical efficacy of DC vaccination. In this phase II trial, metronomic Cyclophosphamide and a Cox-2 inhibitor have been added to a DC vaccine with the intend to dampen immunosuppressive mechanisms. Twenty-eight patients with progressive metastatic melanoma were treated with autologous DCs pulsed with survivin, hTERT, and p53-derived peptides (HLA-A2(+)) or tumor lysate (HLA-A2(-)). Concomitantly the patients were treated with IL-2, Cyclophosphamide, and Celecoxib. The treatment was safe and tolerable. Sixteen patients (57 %) achieved stable disease (SD) at 1st evaluation and 8 patients had prolonged SD (7-13.7 months). The median OS was 9.4 months. Patients with SD had an OS of 10.5 months while patients with progressive disease (PD) had an OS of 6.0 months (p = 0.048) even though there were no differences in prognostic factors between the two groups. Despite the use of metronomic Cyclophosphamide, regulatory T cells did not decrease during treatment. Indirect IFN-γ ELISPOT assays showed a general increase in immune responses from baseline to the time of 4th vaccination. Induction of antigen-specific immune responses was seen in 9 out of 15 screened HLA-A2(+) patients. In conclusion, the number of patients obtaining SD more than doubled and 6-month survival significantly increased compared to a previous trial without Cyclophosphamide and Celecoxib. A general increase in immune responses against the tested peptides was observed.