In earlier studies of the influence of hydroxymethylglutaryl-coenzyme A reductase inhibitors (also known as statins) on colorectal cancer prognosis, investigators reported a reduced rate of cancer-specific mortality. Studies of recurrence are few and small. Using data from Danish registries, we followed 21,152 patients diagnosed with stage I-III colorectal cancer from 2001 to 2011. We estimated the association between statin use in the preceding year and cancer recurrence, cancer-specific mortality, and all-cause mortality rates. We identified 5,036 recurrences, 7,084 deaths from any cause, and 4,066 deaths from colorectal cancer. After adjustment for potential confounders, statin use was not associated with recurrence (adjusted hazard ratio (aHR) = 1.01, 95% confidence interval (CI): 0.93, 1.09), but it was associated with death from colorectal cancer (aHR = 0.72, 95% CI: 0.65, 0.79) and death from any cause (aHR = 0.72, 95% CI: 0.67, 0.76). Statin use in the year preceding recurrence was associated with a reduced risk of cancer-specific mortality (aHR = 0.83, 95% CI: 0.74, 0.92) but also a reduced risk of death from any other cause (aHR = 0.78, 95% CI: 0.61, 1.00). Statin use was not associated with a reduced rate of colorectal cancer recurrence, but it was associated with a reduced rate of cancer-specific mortality, which suggests that there is no cancer-directed benefit; therefore, there is no basis to prescribe statins to colorectal cancer patients who do not have cardiovascular indications.