Screening is recommended to reduce both incidence and mortality of colorectal cancer. Currently, many countries employ fecal occult blood test (FOBT). In Emilia-Romagna (Italy), since 2005, FOBT immunochemical version (FIT) is performed every two years on people aged between 50 and 69 years. A colonoscopy is then carried out on those who are FIT positive. However, FIT shows approximately 65% false positives (non-tumoral bleedings), leading to many negative colonoscopies. The use of an economic and easy-to-use method to check FOBT-positives will improve screening effectiveness, reducing costs to the national health service. This work illustrates the results of a three-year clinical validation protocol (started in 2016) of a patented device composed of a core of nanostructured gas sensors. This device was designed to identify CRC presence by fecal volatile compounds, with a non-invasive, in vitro and low-cost analysis. Feces are, in fact, affected by tumor-volatile biomarkers, produced by cellular peroxidation and metabolic alterations. The protocol consisted in the analysis of fecal samples of FIT-positive subjects, using colonoscopy as a gold standard. A total of 398 samples were analyzed with machine learning techniques, leading to a sensitivity and specificity of 84.1% and 82.4%, respectively, and a positive predictive value of 72% (25–35% for FIT).