Changes in the gut microbiome have already been associated with postoperative complications in major abdominal surgery. However, it is still unclear whether these changes are transient or a long-lasting effect. Therefore, the aim of this prospective clinical pilot study was to examine long-term changes in the gut microbiota and to correlate these changes with the clinical course of the patient. Methods: In total, stool samples of 62 newly diagnosed colorectal cancer patients undergoing primary tumor resection were analyzed by 16S-rDNA next-generation sequencing. Stool samples were collected preoperatively in order to determine the gut microbiome at baseline as well as at 6, 12, and 24 months thereafter to observe longitudinal changes. Postoperatively, the study patients were separated into two groups—patients who suffered from postoperative complications (n = 30) and those without complication (n = 32). Patients with postoperative complications showed a significantly stronger reduction in the alpha diversity starting 6 months after operation, which does not resolve, even after 24 months. The structure of the microbiome was also significantly altered from baseline at six-month follow-up in patients with complications (p = 0.006). This was associated with a long-lasting decrease of a large number of species in the gut microbiota indicating an impact in the commensal microbiota and a long-lasting increase of Fusobacterium ulcerans. The microbial composition of the gut microbiome shows significant changes in patients with postoperative complications up to 24 months after surgery.