Abstract Purpose: Cancer vaccines represent a novel treatment modality with a complementary mode of action addressing a crucial bottleneck for checkpoint inhibitor (CPI) efficacy. CPIs are expected to release brakes in T-cell responses elicited by vaccination, leading to more robust immune responses. Increased antitumor T-cell responses may confer increased antitumor activity in patients with less immunogenic tumors, a subgroup expected to achieve reduced benefit from CPIs alone. In this trial, a telomerase-based vaccine was combined with pembrolizumab to assess the safety and clinical activity in patients with melanoma. Patients and Methods: Thirty treatment-naïve patients with advanced melanoma were enrolled. Patients received intradermal injections of UV1 with adjuvant GM-CSF at two dose levels, and pembrolizumab according to the label. Blood samples were assessed for vaccine-induced T-cell responses, and tumor tissues were collected for translational analyses. The primary endpoint was safety, with secondary objectives including progression-free survival (PFS), overall survival (OS), and objective response rate (ORR). Results: The combination was considered safe and well-tolerated. Grade 3 adverse events were observed in 20% of patients, with no grade 4 or 5 adverse events reported. Vaccination-related adverse events were mostly mild injection site reactions. The median PFS was 18.9 months, and the 1- and 2-year OS rates were 86.7% and 73.3%, respectively. The ORR was 56.7%, with 33.3% achieving complete responses. Vaccine-induced immune responses were observed in evaluable patients, and inflammatory changes were detected in posttreatment biopsies. Conclusions: Encouraging safety and preliminary efficacy were observed. Randomized phase II trials are currently ongoing.