The characterization of the humoral response in cancer patients is becoming a practical alternative to improve early detection. We prepared phage microarrays containing colorectal cancer cDNA libraries to identify phage-expressed peptides recognized by tumor-specific autoantibodies from patient sera. From a total of 1536 printed phages, 128 gave statistically significant values to discriminate cancer patients from control samples. From this, 43 peptide sequences were unique following DNA sequencing. Six phages containing homologous sequences to STK4/MST1, SULF1, NHSL1, SREBF2, GRN, and GTF2I were selected to build up a predictor panel. A previous study with high-density protein microarrays had identified STK4/MST1 as a candidate biomarker. An independent collection of 153 serum samples (50 colorectal cancer sera and 103 reference samples, including healthy donors and sera from other related pathologies) was used as a validation set to study prediction capability. A combination of four phages and two recombinant proteins, corresponding to MST1 and SULF1, achieved an area under the curve of 0.86 to correctly discriminate cancer from healthy sera. Inclusion of sera from other different neoplasias did not change significantly this value. For early stages (A+B), the corrected area under the curve was 0.786. Moreover, we have demonstrated that MST1 and SULF1 proteins, homologous to phage-peptide sequences, can replace the original phages in the predictor panel, improving their diagnostic accuracy.