Colorectal cancer (CRC) is one of the most common cancers and is the second leading cause of cancer-related death in the world. Due to the westernization of diets, young patients with CRC are often diagnosed at advanced stages with an associated poor prognosis. Improved lifestyle choices are one way to minimize CRC risk. Among diet choices is the inclusion of bee propolis, long recognized as a health supplement with anticancer activities. Understanding the effect of propolis on the gut environment is worth exploring, and especially its associated intratumoral immune changes and its anticancer effect on the occurrence and development of CRC. In this study, early stage CRC was induced with 1,2-dimethylhydrazine (DMH) and dextran sulfate sodium (DSS) for one month in an animal model, without and with propolis administration. The phenotypes of early stage CRC were evaluated by X-ray microcomputed tomography and histologic examination. The gut immunity of the tumor microenvironment was assessed by immunohistochemical staining for tumor-infiltrating lymphocytes (TILs) and further comparative quantification. We found that the characteristics of the CRC mice, including the body weight, tumor loading, and tumor dimensions, were significantly changed due to propolis administration. With further propolis administration, the CRC tissues of DMH/DSS-treated mice showed decreased cytokeratin 20 levels, a marker for intestinal epithelium differentiation. Additionally, the signal intensity and density of CD3 and CD4 TILs were significantly increased and fewer forkhead box protein P3 (FOXP3) lymphocytes were observed in the lamina propria. In conclusion, we found that propolis, a natural supplement, potentially prevented CRC progression by increasing CD3 and CD4 TILs and reducing FOXP3 lymphocytes in the tumor microenvironment of early stage CRC. Our study could suggest a promising role for propolis in complementary medicine as a food supplement to decrease or prevent CRC progression.