Background Higher concentrations of 25-hydroxyvitamin D3 [25(OH)D3] at diagnosis are associated with a lower mortality risk in colorectal cancer (CRC) patients. However, magnesium and calcium are important in vitamin D metabolism. Objectives We aimed to investigate 25(OH)D3, magnesium, or calcium and their interaction among patients with CRC in relation to recurrence and all-cause mortality. Methods The study population included 1169 newly diagnosed stage I–III CRC patients from 2 prospective cohorts. Associations between 25(OH)D3 concentrations, magnesium or calcium intake through diet and/or supplements at diagnosis, and recurrence and all-cause mortality were evaluated using multivariable Cox proportional hazard models. The interaction between 25(OH)D3 and magnesium or calcium was assessed by investigating 1 ) joint compared with separate effects, using a single reference category; and 2 ) the effect estimates of 1 factor across strata of another. Results Serum 25(OH)D3, calcium, and magnesium, alone and their interactions, were not associated with recurrence. Serum 25(OH)D3 concentrations seemed to be associated with all-cause mortality. An inverse association between magnesium intake (HRQ3 vs. Q1: 0.55; 95% CI: 0.32, 0.95 and HRQ4 vs. Q1: 0.65; 95% CI: 0.35, 1.21), but not calcium intake, and all-cause mortality was observed. When investigating the interaction between 25(OH)D3 and magnesium, we observed the lowest risk of all-cause mortality in patients with sufficient vitamin D concentrations (≥50 nmol/L) and a high magnesium intake (median split) (HR: 0.53; 95% CI: 0.31, 0.89) compared with patients who were vitamin D deficient (<50 nmol/L) and had a low magnesium intake. No interactions between calcium and vitamin D in relation to all-cause mortality were observed. Conclusions Our findings suggest that the presence of an adequate status of 25(OH)D3 in combination with an adequate magnesium intake is essential in lowering the risk of mortality in CRC patients, yet the underlying mechanism should be studied. In addition, diet and lifestyle intervention studies are needed to confirm our findings. The COLON study was registered at clinicaltrials.gov as NCT03191110. The EnCoRe study was registered at trialregister.nl as NTR7099.