Blood‐based protein biomarkers may be an attractive option for early detection of colorectal cancer (CRC). Here, we used a two‐stage design to measure 275 protein markers by proximity extension assay (PEA), first in plasma samples of a discovery set consisting of 98 newly diagnosed CRC cases and 100 age‐ and gender‐matched controls free of neoplasm at screening colonoscopy. An algorithm predicting the presence of early‐ or late‐stage CRC was derived by least absolute shrinkage and selection operator regression with .632+ bootstrap method, and the algorithms were then validated using PEA again in an independent validation set consisting of participants of screening colonoscopy with and without CRC (n = 56 and 102, respectively). Three different signatures for all‐, early‐, and late‐stage CRC consisting of 9, 12, and 11 protein markers were obtained in the discovery set with areas under the curves (AUCs) after .632 + bootstrap adjustment of 0.92, 0.91, and 0.96, respectively. External validation among participants of screening colonoscopy yielded AUCs of 0.76 [95% confidence interval (95% CI), 0.67–0.84], 0.75 (95% CI, 0.62–0.87), and 0.80 (95% CI, 0.68–0.89) for all‐, early‐, and late‐stage CRC, respectively. Although the identified protein markers are not competitive with the best available stool tests, these proteins may contribute to the development of powerful blood‐based tests for CRC early detection in the future.