Background: HLA-A*02, a common allele in the Scandinavian population, is a negative prognostic factor in epithelial ovarian cancer. It is a strong predictor of patient outcome, only inferior to clinical staging. This prognostic trait in epithelial ovarian cancer is stronger by the presence of the gene compared with the expression of its protein, MHC class I. Microsatellite instability (MSI) is used as a biomarker for prognosis and is suggested an increased tumor mutational burden which can make the tumor more susceptible for T cell mediated immunotherapy. Our aim was to analyze the prognostic markers HLA-A*02 genotype, MHC class I on tumor cells, the CD8+ lymphocyte infiltration and MSI status in colon cancer patients with randomized treatment. Methods: Clinical information and primary tumors were collected from 520 colon cancer patients and followed for overall survival for 120 months. Patients hade stage II and III colon cancer and were randomized to surgery alone or surgery and adjuvant chemotherapy. HLA-A*02 genotype was determined by conventional PCR. MHC class I, MSI status and CD8+ lymphocyte infiltration were determined by immunohistochemistry. Results: Female patients with a stage III tumor and HLA-A*02 genotype had a better outcome if they had received adjuvant chemotherapy instead of just surgery (p = 0.03), whereas this was not the case for patients with other HLA-A genotypes or in the male patients where HLA-type did not correlate to outcome. MHC class I expression did not act as a prognostic factor, however the presence of CD8+ lymphocytes in the invasive margin and inside the tumor was a positive prognostic factor for overall survival (p = 0.01), although only statistically significant in the male patients (p = 0.03). 21% patients had a tumor with MSI (23% of the female and 19% of the male patients respectively). MSI tumors had a slightly better outcome and this was irrespective of gender and HLA-type. Conclusions: The prognostic traits of HLA-A*02 appear in this colon cancer cohort to act differently in male and female patients. Also CD8+ infiltration is different between genders. These findings suggest that men and women may have two different immune responses to malignancy.