Background and Objectives: High recurrence rates of Stages II and IIIA melanoma make close follow-up essential, especially with new adjuvant therapies for metastatic disease. However, there are currently no consensus guidelines for routine imaging for Stages IIB, IIC, and IIIA melanoma. The study's aim is to determine the utility of 18F-fluorodeoxyglucose (18F-FDG) positron emission tomography/computed tomography (PET/CT) for detecting asymptomatic recurrence of melanoma after primary surgical resection. Methods: This retrospective cohort study included 158 patients with the American Joint Committee on Cancer 8th edition Stages IIB, IIC, or IIIA cutaneous melanoma who underwent an 18F-FDG PET/CT from 2010 to 2020. We retrospectively analyzed clinical data after a median follow-up time of 39 months. Results: We calculated a positive predictive value (PPV) of 32% (95% confidence interval: 11%–53%) for 154 routine PET/CTs, including six true positives and 13 false positives (FPs). PPV was 33% for Stage IIB, 50% for Stage IIC, and 14% for Stage IIIA. FPs were mostly benign or inflammatory foci (75%), and some other malignancies were found (21%). Conclusions: This cohort of patients imaged for high-risk melanoma demonstrated a high FP rate and low PPV. These findings suggest that routine surveillance with 18F-FDG PET/CT may not be indicated for monitoring recurrence in this population.