Background Considering the complications that colostomies may cause, patient self-assessments of their social, emotional, physical, sexual and functional conditions may help their surgeons to evaluate the impact of their interventions or use supplementary methods to maintain patient functional status or decrease its loss to the minimum level. The aim of this study was to evaluate the Quality of Life in Iranian patients with colostomies and to compare the age and gender differences among them. Method This cross-sectional study was conducted from 2009 to 2010 to evaluate the quality of life of 96 patients who had undergone surgery for rectal cancer and had permanent colostomies. The European Organization for Research and Treatment of Cancers Quality of Life Questionnaire (EORTC QLQ)-C30 and the EORTC QLQ-CR38 were used to assess patient Quality of Life. Results The mean scores for the functional subscales were as follows: Physical Function, 70.9 (±2.2); Role Function, 68.4 (±2.6); Emotional Function, 56.9 (±2.7); Cognitive Function, 68.7 (± 2.6); and Social Function, 64.2 (±3.3). The EORTC questionnaires showed significant differences between males and females. Males had better body image scores. Sexual Function and Sexual Enjoyment were impaired in both males and females, but males had significantly higher scores and better roles in Physical and Sexual Functions. More sexual enjoyment problems in older ages were observed in both males and females. Conclusion Having a colostomy was associated with a high level of emotional and sexual function impairment. The differing challenges between males and females should encourage us to design sex-specific interventions that improve the quality of life in this group of patients.