To discover serological colorectal cancer (CRC) markers, we analyzed cell line secretome to gather proteins of higher potential to be secreted from tissues into circulation. A total of 898 human proteins were identified, of which 62.2% were predicted to be released or shed from cells. The identified proteins were compared with tissue proteomes to find candidate proteins whose expressions were elevated in tumor tissues compared with normal tissues as revealed by (i) quantitative proteomic analysis based on cICAT and mTRAQ or (ii) data mining of immunohistochemical images piled in Human Protein Atlas database. By applying various stringent criteria, 11 candidate proteins were selected. Among these, we validated an significant increase (p = 0.0018) of melanotransferrin (TRFM) at the plasma level of CRC patients through Western blotting, using 130 plasma samples containing 30 healthy controls, 80 CRC patients, and 20 patients of other diseases. Finally, we measured the expression level of TRFM in 325 plasma samples containing 77 healthy controls and 228 CRC patients (34.6 ± 4.2 ng/mL and 67.0 ± 6.4 ng/mL, p < 0.0001) through ELISA and demonstrated the area under the receiver operating characteristic curve of 0.723 (p < 0.0001) with a 92.5% specificity, 48.2% sensitivity, and 95.7% positive predictive value. Furthermore, unlike CEA and PAI-1, up-regulation of TRFM in pathological stages I & II groups compared with stages III & IV groups lead us to expect the use TRFM for early-stage diagnosis of CRC. In this study, we suggest TRFM as a potential serological marker for CRC and expect our discovery strategy to help identify highly cancer-specific and body-fluid-accessible biomarkers.