Patients with newly resected stage II melanoma (n = 104) were randomized to receive adjuvant vitamin D3 (100,000 IU every 50 days) or placebo for 3 years to investigate vitamin D3 protective effects on developing a recurrent disease. Median age at diagnosis was 50 years, and 43% of the patients were female. Median serum 25-hydroxy vitamin D (25OHD) level at baseline was 18 ng/mL, interquartile range (IQ) was 13–24 ng/mL, and 80% of the patients had insufficient vitamin D levels. We observed pronounced increases in 25OHD levels after 4 months in the active arm (median 32.9 ng/mL; IQ range 25.9–38.4) against placebo (median 19.05 ng/mL; IQ range 13.0–25.9), constantly rising during treatment. Remarkably, patients with low Breslow score (<3 mm) had a double increase in 25OHD levels from baseline, whereas patients with Breslow score ≥3 mm had a significantly lower increase over time. After 12 months, subjects with low 25OHD levels and Breslow score ≥3 mm had shorter disease-free survival (p = 0.02) compared to those with Breslow score <3 mm and/or high levels of 25OHD. Adjusting for age and treatment arm, the hazard ratio for relapse was 4.81 (95% CI: 1.44–16.09, p = 0.011). Despite the evidence of a role of 25OHD in melanoma prognosis, larger trials with vitamin D supplementation involving subjects with melanoma are needed.