Abstract Purpose: A phase Ib/II clinical trial was conducted to evaluate the safety and efficacy of the combination of all-trans retinoic acid (ATRA) with pembrolizumab in patients with stage IV melanoma. Patients and Methods: Anti–PD-1 naïve patients with stage IV melanoma were treated with pembrolizumab plus supplemental ATRA for three days surrounding each of the first four pembrolizumab infusions. The primary objective was to establish the MTD and recommended phase II dose (RP2D) of the combination. The secondary objectives were to describe the safety and toxicity of the combined treatment and to assess antitumor activity in terms of (i) the reduction in circulating myeloid-derived suppressor cell (MDSC) frequency and (ii) progression-free survival (PFS). Results: Twenty-four patients were enrolled, 46% diagnosed with M1a and 29% with M1c stage disease at enrollment. All patients had an ECOG status ≤1, and 75% had received no prior therapies. The combination was well tolerated, with the most common ATRA-related adverse events being headache, fatigue, and nausea. The RP2D was established at 150 mg/m2 ATRA + 200 mg Q3W pembrolizumab. Median PFS was 20.3 months, and the overall response rate was 71%, with 50% of patients experiencing a complete response, and the 1-year overall survival was 80%. The combination effectively lowered the frequency of circulating MDSCs. Conclusions: With a favorable tolerability and high response rate, this combination is a promising frontline treatment strategy for advanced melanoma. Targeting MDSCs remains an attractive mechanism to enhance the efficacy of immunotherapies, and this combination merits further investigation.