Background: Anxiety and depression are common in patients with cancer. The aim of this study is to determine the prevalence of anxiety and depression symptoms in colorectal cancer (CRC) patients awaiting elective surgery and whether there is an association with their preoperative nutritional status and postoperative mortality. Methods: A prospective study was conducted on 215 patients with CRC proposed for surgery. Data about nutritional status were collected using the Global Leadership Initiative on Malnutrition (GLIM) criteria, while anxiety and depression symptoms data were collected using Hospital Anxiety and Depression Scale (HADS). Results: HADS detected possible anxiety in 41.9% of patients, probable anxiety in 25.6%, possible depression in 21.9%, and probable depression in 7.9%. GLIM criteria found 116 (53.9%) patients with malnutrition. The HADS score for depression subscale was significantly higher in malnourished patients than in well-nourished (5.61 ± 3.65 vs. 3.95 ± 2.68; p = 0.001). After controlling for potential confounders, malnourished patients were 10.19 times more likely to present probable depression (95% CI 1.13–92.24; p = 0.039). Mortality was 1.9%, 4,2%, and 5.6% during admission and after 6 and 12 months, respectively. Compared to patients without depressive symptomatology, in patients with probable depression, mortality risk was 14.67 times greater (95% CI 1.54–140.21; p = 0.02) during admission and 6.62 times greater (95% CI 1.34–32.61; p = 0.02) after 6 months. Conclusions: The presence of anxiety and depression symptoms in CRC patients awaiting elective surgery is high. There is an association between depression symptoms, preoperative nutritional status, and postoperative mortality.