Although colorectal cancer (CRC) is the second leading cause of death in developed countries, current diagnostic tests for early disease stages are suboptimal. We have performed a combination of UHPLC-MS metabolomics and 16S microbiome analyses on 224 feces samples in order to identify early biomarkers for both advanced adenomas (AD) and CRC. We report differences in fecal levels of cholesteryl esters and sphingolipids in CRC. We identified Fusobacterium, Parvimonas and Staphylococcus to be increased in CRC patients and Lachnospiraceae family to be reduced. We finally described Adlercreutzia to be more abundant in AD patients’ feces. Integration of metabolomics and microbiome data revealed tight interactions between bacteria and host and performed better than FOB test for CRC diagnosis. This study identifies potential early biomarkers that outperform current diagnostic tools and frame them into the stablished gut microbiota role in CRC pathogenesis.