People undergoing investigations for suspected cancer have to undergo a number of investigations before they know their full diagnosis and treatment plan. We examined predictors of distress among patients undergoing staging investigations for suspected colorectal or lung cancer. Patients were prospectively recruited to two multi-centre trials comparing WB-MRI with standard scans. Patients completed a questionnaire, administered at trial recruitment, measuring demographic and psychological variables (n = 129, 66 colorectal, 63 lung; median age 66.4, range: 31-89). Predictors of distress were analysed using logistic regression. Forty percent of patients reported high distress (a score of 4 or higher on the GHQ-12). Higher deprivation and greater intolerance of uncertainty (IU) predicted high distress in both unadjusted (low deprivation: OR 0.352, 95% CIs 0.144 to 0.860, p = 0.022; IU: OR 1.972, 95% CIs: 1.357 to 2.865, p < 0.001) and adjusted analyses (low deprivation: OR 0.243, 95% CIs 0.083 to 0.714, p = 0.010; IU: OR 2.231, 95% CIs 1.429 to 3.485, p < 0.001). Age, gender, presence of comorbid illness, cancer type, probable knowledge of cancer diagnosis, and a final diagnosis of cancer did not predict high distress. Future research should examine how to reduce distress in patients undergoing investigations for cancer, particularly among those who find uncertainty difficult to manage.