Colorectal cancer (CRC) is the third most common malignancy and the second most common cause of cancer-related deaths worldwide. While CRC screening is already part of organized programs in many countries, there remains a need for improved screening tools. In recent years, a potential approach for cancer diagnosis has emerged via the analysis of volatile organic compounds (VOCs) using sensor technologies. The main goal of this study was to demonstrate and evaluate the diagnostic potential of a table-top breath analyzer for detecting CRC. Breath sampling was conducted and CRC vs. non-cancer groups (105 patients with CRC, 186 non-cancer subjects) were included in analysis. The obtained data were analyzed using supervised machine learning methods (i.e., Random Forest, C4.5, Artificial Neural Network, and Naïve Bayes). Superior accuracy was achieved using Random Forest and Evolutionary Search for Features (79.3%, sensitivity 53.3%, specificity 93.0%, AUC ROC 0.734), and Artificial Neural Networks and Greedy Search for Features (78.2%, sensitivity 43.3%, specificity 96.5%, AUC ROC 0.735). Our results confirm the potential of the developed breath analyzer as a promising tool for identifying and categorizing CRC within a point-of-care clinical context. The combination of MOX sensors provided promising results in distinguishing healthy vs. diseased breath samples. Its capacity for rapid, non-invasive, and targeted CRC detection suggests encouraging prospects for future clinical screening applications.