Colorectal cancer (CRC) is the third leading cause of cancer mortality for both men and women, and the second leading cause of cancer death for men and women combined. If detected early, before metastasis has occurred, survival following surgical resection of the tumor is > 90%. Early detection is therefore critical for effective disease surveillance. Unfortunately, current biomarker assays lack the necessary sensitivity and specificity for reliable early disease detection. Development of new robust, non- or minimally invasive specific and sensitive biomarkers or panels with improved compliance and performance is therefore urgently required. The use of fecal samples offers several advantages over other clinical biospecimens (e.g., plasma or serum) as a source of CRC biomarkers, including: collection is noninvasive, the test can be performed at home, one is not sample limited, and the stool effectively samples the entire length of the inner bowel wall contents (including tumor) as it passes down the gastrointestinal tract. Recent advances in mass spectrometry now facilitate both the targeted discovery and validation of potential CRC biomarkers. We describe, herein, detailed protocols that can be used to mine deeply into the fecal proteome to reveal candidate proteins, identify proteotypic/unitypic peptides (i.e., peptides found in only a single known human protein that serve to identify that protein) suitable for sensitive and specific quantitative multiplexed analysis, and undertake high-throughput analysis of clinical samples. Finally, we discuss future directions that may further position this technology to support the current switch in translation research toward personalized medicine.