PURPOSE: Among long-term (>or=5 y) colorectal cancer survivors with permanent ostomy or anastomosis, we compared the incidence of medical and surgical complications and examined the relationship of complications with health-related quality of life. BACKGROUND: The incidence and effects of complications on long-term health-related quality of life among colorectal cancer survivors are not adequately understood. METHODS: Participants (284 survivors with ostomies and 395 survivors with anastomoses) were long-term colorectal cancer survivors enrolled in an integrated health plan. Health-related quality of life was assessed via mailed survey questionnaires from 2002 to 2005. Information on colorectal cancer, surgery, comorbidities, and complications was obtained from computerized data and analyzed by use of survival analysis and logistic regression. RESULTS: Ostomy and anastomosis survivors were followed up for an average of 12.1 and 11.2 years, respectively. Within 30 days of surgery, 19% of ostomy survivors and 10% of anastomosis survivors experienced complications (P < .01). From 31 days on, the percentages were 69% and 67% (after adjustment, P < .001). Bleeding and postoperative infection were common early complications. Common long-term complications included hernia, urinary retention, hemorrhage, skin conditions, and intestinal obstruction. Ostomy was associated with long-term fistula (odds ratio, 5.4; 95% CI 1.4-21.2), and among ostomy survivors, fistula was associated with reduced health-related quality of life (P < .05). CONCLUSIONS: Complication rates remain high despite recent advances in methods of surgical treatment. Survivors with ostomy have more complications early in their survivorship period, but complications among anastomosis survivors catch up after 20 years, when the 2 groups have convergent complication rates. Among colorectal cancer survivors with ostomy, fistula has especially important implications for health-related quality of life.