Background: The effect of routine imaging in melanoma surveillance is unknown. In 2016, Denmark was the first country in the world to implement routine imaging with positron emission tomography-computed tomography with fluorodeoxyglucose (FDG PET-CT) in a nationwide, population-based surveillance program. This study aimed to determine the impact of surveillance with routine FDG PET-CT on hazard, cumulative incidence, and absolute risk of overall, locoregional, and distant recurrence detection in patients with stage IIB to IIID cutaneous melanoma. Methods: This retrospective, population-based, nationwide cohort study used prospectively collected data from five national health registries to compare hazard, cumulative incidence, and absolute risk of recurrence in patients with cutaneous melanoma diagnosed in 2008–2010 (cohort 1, followed with clinical examinations) and patients with cutaneous melanoma diagnosed in 2016–2017 (cohort 2, followed with clinical examinations and routine FDG PET-CT at 6, 12, 24, and 36 months). Results: The study included 1480 patients with stage IIB to IIID cutaneous melanoma. Cumulative incidences of overall and distant recurrence were higher in cohort 2, with a peak difference at three years (32.3 % vs 27.5 % and 25.8 % vs. 18.5 %, respectively). The hazard of recurrence was higher in cohort 2 during the first two years, with hazard rates for overall and distant recurrence of 1.16 (95 % confidence interval [CI], 0.93–1.44) and 1.51 (95 % CI, 1.16–1.96), respectively. The patterns persisted in absolute risk estimates. Conclusions: Patients with stage IIB to IIID melanoma followed with routine FDG PET-CT had a 51 % increased hazard of distant recurrence detection within the first two years of surveillance. Future studies must determine whether this earlier recurrence detection translates into improved survival.