Immunotherapy for metastatic melanoma offers great promise but, to date, only a subset of patients have responded. There is an urgent need to identify ways of allocating patients to the most beneficial therapy, to increase survival and decrease therapy-associated morbidity and costs. Blood-based biomarkers are of particular interest because of their straightforward implementation in routine clinical care. We sought to identify markers for dendritic cell (DC) vaccine-based immunotherapy against metastatic melanoma through gene expression analysis of peripheral blood mononuclear cells. A large-scale microarray analysis of 74 samples from two treatment centers, taken directly after the first round of DC vaccination, was performed. We found that phosphatidylethanolamine binding protein 1 (PEBP1)/Raf Kinase inhibitory protein (RKIP) expression can be used to identify a significant proportion of patients who performed poorly after DC vaccination. This result was validated by q-PCR analysis on blood samples from a second cohort of 95 patients treated with DC vaccination in four different centers. We conclude that low PEBP1 expression correlates with poor overall survival after DC vaccination. Intriguingly, this was only the case for expression of PEBP1 after, but not prior to, DC vaccination. Moreover, the change in PEBP1 expression upon vaccination correlated well with survival. Further analyses revealed that PEBP1 expression positively correlated with genes involved in T cell responses but inversely correlated with genes associated with myeloid cells and aberrant inflammation including STAT3, NOTCH1, and MAPK1. Concordantly, PEBP1 inversely correlated with the myeloid/lymphoid-ratio and was suppressed in patients suffering from chronic inflammatory disease.