Anti-PD-1 (aPD1) therapy is an effective treatment for metastatic melanoma (MM); however, >50% of the patients progress due to resistance. Improved combination therapies enhancing aPD1 efficacy without leading to increased toxicity are needed. In this non-randomized phase I/II study (ClinicalTrials.gov: NCT03047928), we treated 30 aPD1 naive MM patients with a novel immune-modulatory vaccine (IO102/IO103) activating indoleamine 2,3-dioxygenase (IDO) and programmed death ligand-1 (PD-L1) specific T-cells combined with nivolumab. The vaccine has a dual mechanism of action, targeting both immunosuppressive cells and tumour cells expressing IDO/PD-L1. The vaccine was administered every two weeks for the first 6 injections and every fourth week thereafter, for up to 15 vaccines. Nivolumab was administered every two weeks (3mg/kg) for a maximum of 2 years. The primary endpoint was safety and feasibility; the systemic toxicity profile was comparable to nivolumab monotherapy, except for local and transient reactions at the vaccination site. Secondary endpoints were clinical efficacy and immunogenicity. An ORR of 80% (CI: 62.7-90.5%) was reached, with the majority of 43% (CI: 27.4-60.8%) achieving a complete response. After a median follow-up of 22.9 months, the median PFS was 26 months (CI: 15.4-69). Vaccine-specific responses were detected in vitro in blood from >93% of the patients on vaccination, suggesting the induction of memory response up to 6 months after the last vaccine. Vaccine reactive T-cells comprised both CD4+ and CD8+ T-cells. Paired biopsies from five patients with matched longitudinal PBMCs showed T-cell influx at the tumour site of peripherally expanded T-cells in responding patients and general enrichment of IDO and PD-L1 clones after treatment. These unprecedented clinical efficacy data support further validation in a larger randomized trial, to confirm the clinical potential of this first-in-class immunomodulating vaccine.