BACKGROUND: Malignant melanoma is the deadliest form of skin cancer and is refractory to conventional chemotherapy and radiotherapy. Therefore alternative approaches to treat this disease, such as immunotherapy, are needed. Melanoma vaccine design has mainly focused on targeting CD8+ T cells. Activation of effector CD8+ T cells has been achieved in patients, but provided limited clinical benefit, due to immune-escape mechanisms established by advanced tumors. We have previously shown that alphavirus-based virus-like replicon particles (VRP) simultaneously activate strong cellular and humoral immunity against the weakly immunogenic melanoma differentiation antigen (MDA) tyrosinase. Here we further investigate the antitumor effect and the immune mechanisms of VRP encoding different MDAs. METHODOLOGY/PRINCIPAL FINDINGS: VRP encoding different MDAs were screened for their ability to prevent the growth of the B16 mouse transplantable melanoma. The immunologic mechanisms of efficacy were investigated for the most effective vaccine identified, focusing on CD8+ T cells and humoral responses. To this end, ex vivo immune assays and transgenic mice lacking specific immune effector functions were used. The studies identified a potent therapeutic VRP vaccine, encoding tyrosinase related protein 2 (TRP-2), which provided a durable anti-tumor effect. The efficacy of VRP-TRP2 relies on a novel immune mechanism of action requiring the activation of both IgG and CD8+ T cell effector responses, and depends on signaling through activating Fcγ receptors. CONCLUSIONS/SIGNIFICANCE: This study identifies a VRP-based vaccine able to elicit humoral immunity against TRP-2, which plays a role in melanoma immunotherapy and synergizes with tumor-specific CD8+ T cell responses. These findings will aid in the rational design of future immunotherapy clinical trials.