Objectives: Fusobacterium nucleatum, which is the predominant subgingival microbial species found in chronic periodontitis, has been recently proposed as a risk factor for both the initiation and progression of colorectal cancer. We evaluated whether the number of teeth, which represents oral health, is a marker for the prognosis of patients with colorectal cancer. Methods: This retrospective single-center study recruited 179 patients who underwent primary colorectal cancer resection with curative intent between 2015 and 2017. The baseline characteristics and survival were analyzed according to the number of teeth observed in dental panoramic radiographs taken before surgical resection as a part of the perioperative surveillance for oral function and hygiene. Results: The median number of teeth was 20 (interquartile range: 6-25), including 28 patients with no teeth. Patients with 20 or more teeth had better overall survival (p = 0.002) and colorectal cancer-specific survival (p = 0.032) than those with less than 20 teeth. Multivariate analyses confirmed that the number of teeth was a significant prognostic factor for overall survival (p = 0.045) but not for colorectal cancer-specific survival (p = 0.258). We also took a propensity score-weighting approach using inverse probability weighting, and the p-values of the number of teeth were 0.032 for overall survival and 0.180 for colorectal cancer-specific survival. Conclusions: A low number of teeth, which can be easily and noninvasively assessed, has been a poor prognostic factor for overall survival in colorectal cancer patients who underwent surgery with curative intent.