Colorectal cancer (CRC) is the second overall leading cause of cancer death in the United States, with recurrence being a frequent cause of mortality. Approaches to improve disease-free survival (DFS) are urgently needed. The gut microbiome, reflected in fecal samples, is likely mechanistically linked to CRC progression and may serve as a non-invasive biomarker. Accordingly, we leveraged baseline fecal samples from N = 166 stage I-III CRC patients in the ColoCare Study, a prospective cohort of newly diagnosed CRC patients. We sequenced the V3 and V4 regions of the 16S rRNA gene to characterize fecal bacteria. We calculated estimates of alpha diversity, beta diversity, and a priori- and exploratory-selected bacterial presence/absence and relative abundance. Associations of microbial metrics with DFS were estimated using multivariable Cox proportional hazards models. We found that alpha diversity was strongly associated with improved DFS, most strongly among rectal cancer patients (Shannon HR