Currently, cancer vaccine therapy for melanoma has a 2-fold focus. On the one hand, advances have been aimed at improving the effectiveness of melanoma vaccines based on a greater understanding of melanoma tumor cell biology. On the other hand, there is increasing evidence that the immune system, our defense against tumors, also inadvertently plays a supportive role in promoting the development and progression of tumors. Hence, two opposing forces 'hanging in the balance' dictate patients' responses to melanoma: tumor cell biology and the status of the immune system. Recent developments in our understanding of both of these aspects have provided new leads and insights for novel ways to improve vaccine design and add to the melanoma vaccine armory. As the focus of immunotherapy shifts its aim towards the tumor microenvironment, we are now developing the ability to program the immune responses raised by vaccination against melanoma. The aim here is to prevent myeloid and regulatory T-cell-mediated immune suppression as well as to counteract tumor-derived factors capable of suppressing immune responses. A redirected strategy for vaccine immunotherapy is proposed based on our greater understanding of tumor immunity. Using a combination therapy of immune-potentiating melanoma vaccines together with adjuvants for overcoming the immunosuppressive forces will allow us to activate protective immunity against melanoma. Other cancer vaccines (i.e. colon or renal) are already offering reasons for hope and expectation that vaccine immunotherapy will also produce successful outcomes for patients with melanoma.