Millet is an important cereal food and exhibits multiple biological activities, including immunomodulation, antioxidant, antifungal and anti-hyperglycemia effects. Herein, we describe a novel 35kDa protein with anti-cancer property, named FMBP, which was extracted and purified from foxtail millet bran by cell-based screening. FMBP is highly homologous to peroxidase as revealed by mass spectrometry and gene sequencing analysis. Furthermore, in vivo anti-tumor results implicated that the novel protein FMBP had the ability to suppress xenografted tumor growth in nude mice. Mechanistically, FMBP is able to suppress colon cancer cell growth through induction of G1 phase arrest and also causes a loss of mitochondrial transmembrane potential which results in caspase-dependent apoptosis in colon cancer cells. Notably, FMBP has much lower toxicity in normal colon epithelial cells. Taken together, FMBP has targeted anti-colon cancer effects and may serve as a therapeutic agent against colon cancer.