Background: β-adrenergic receptors are upregulated in melanoma cells and contribute to an immunosuppressive, pro-tumorigenic microenvironment. This study investigated the prognostic and predictive value of β-adrenoreceptor blockade by β-blockers in the EORTC1325/KEYNOTE-054 randomised controlled trial. Methods: Patients with resected stage IIIA, IIIB or IIIC melanoma and regional lymphadenectomy received 200 mg of adjuvant pembrolizumab (n = 514) or placebo (n = 505) every three weeks for one year or until recurrence or unacceptable toxicity. At a median follow-up of 3 years, pembrolizumab prolonged recurrence-free survival (RFS) compared to placebo (hazard ratio (HR) 0.56, 95% confidence interval (CI) 0.47–0.68). β-blocker use was defined as oral administration of any β-blocker within 30 days of randomisation. A multivariable Cox proportional hazard model was used to estimate the HR for the association between the use of β-blockers and RFS. Results: Ninety-nine (10%) of 1019 randomised patients used β-blockers at baseline. β-blockers had no independent prognostic effect on RFS: HR 0.96 (95% CI 0.70–1.31). The HRs of RFS associated with β-blocker use were 0.67 (95% CI 0.38–1.19) in the pembrolizumab arm and 1.15 (95% CI 0.80–1.66) in the placebo arm. The HR of RFS associated with pembrolizumab compared to placebo was 0.34 (95% CI 0.18–0.65) among β-blocker users and 0.59 (95% CI 0.48–0.71) among those not using β-blockers. Conclusions: This study suggests no prognostic effect of β-blockers in resected high-risk stage III melanoma. However, β-blockers may predict improved efficacy of adjuvant pembrolizumab treatment. The combination of immunotherapy with β-blockers merits further investigation. This study is registered with ClinicalTrials.gov, NCT02362594, and EudraCT, 2014-004944-37.