Psychosocial correlates are one of the crucial determinants for the uptake of colorectal cancer (CRC) screening by the pre-eligible population. The present study aimed to identify the psychosocial correlates of colorectal cancer screening and determine their associated factors among the Saudi population in the Najran region, Saudi Arabia. Using a validated questionnaire, we assessed five constructs of psychosocial correlates of CRC screening among 790 participants aged 45 years and above. The five constructs were salience and coherence, cancer worries, perceived susceptibility, response efficacy, and social influence. Of the studied population, less than 50% agreed with most of the five constructs’ statements, and 27.5% preferred to follow their family members’ advice. Significantly higher mean scores (±SD) were identified for the male gender (7.38 ± 2.15, p = 0.027) and participants working in government sectors (7.60 ± 2.03, p = 0.027) in the cancer worries construct, while the mean (±SD) scores of perceived susceptibility were significantly higher among married participants (14.38 ± 4.10, p = 0.023) and smokers (14.95 ± 3.92, p = 0.041). Our survey results could help policymakers to implement focused health education programs for the pre-eligible population on the importance of the uptake of CRC screening. Furthermore, it is recommended to carry out exploratory mixed-method surveys in other regions of Saudi Arabia to understand the region’s specific psychosocial correlates towards CRC screening