To determine how quality of life changes over time and to assess gender-related differences in quality of life of rectal cancer patients we conducted a 5-year study. Little is known about how quality of life (QoL) changes over time in patients after surgery for rectal cancer, and whether gender of the patients is associated with a different perception of QoL. The aim of this study was to assess prospectively, changes in quality of life after surgery for rectal cancer, with a focus on gender related differences. Over a 5-year period, the EORTC-QLQ-C-30 and a tumor-specific module were prospectively administered to patients before surgery, at discharge, 3, 6, 12, and 24 months postoperatively. Comparisons were made between female and male patients. A total of 519 patients participated in the study, 264 men and 255 women. The two groups were comparable in terms of surgical procedures, adjuvant treatment, tumor stage, and histology. Most QoL scores dropped significantly below baseline in the early postoperative period. From the third month onward, global health, emotional and physical functioning, improved. Female gender was associated with significantly worse global health and physical functioning and with higher scores on treatment strain and fatigue. Men reported difficulties with sexual enjoyment; furthermore, over time, sexual problems created high levels of strain in men, worse than baseline levels in the early postoperative period. These problems tended to continue over the course of time. The findings in this study confirm that QoL changes after surgery and differs between men and women. Women appear to be affected by impaired physical functioning and global health. Female gender is associated with significantly higher fatigue levels and increased strain values after surgery. Through impaired sexual enjoyment, men are put more under strain than woman.