Purpose: To investigate the prognostic value of multiple cell cycle-associated proteins in a large series of stage II and III colon cancers. Methods: From formalin-fixed, paraffin-embedded tumor samples of 386 patients with stage II and III colon cancer, DNA was isolated and tissue microarrays were constructed. Tissue microarray slides were immunohistochemically stained for p21, p27, p53, epidermal growth factor receptor, Her2/Neu, β-catenin, cyclin D1, Ki-67, thymidylate synthase, and Aurora kinase A (AURKA). Polymerase chain reaction-based microsatellite instability analysis was performed to allow for stratification of protein expression by microsatellite instability status. Results: Overall, low p21, high p53, low cyclin D1, and high AURKA expression were significantly associated with recurrence (P = 0.01, P < 0.01, P = 0.04, and P < 0.01, respectively). In stage II patients who did not receive adjuvant chemotherapy (n = 190), significantly more recurrences were observed in case of low-p21 and high-p53-expressing tumors (P < 0.01 and P = 0.03, respectively). In stage III patients who did not receive chemotherapy, high p53 expression was associated with recurrence (P = 0.02), and in patients who received chemotherapy, high AURKA expression was associated with relapse (P < 0.01). In patients with microsatellite stable tumors, high levels of p53 and AURKA were associated with recurrence (P = 0.01 and P < 0.01, respectively). Multivariate analysis showed p21 (odds ratio 1.6, 95% confidence interval 0.9-2.8) and AURKA (odds ratio 2.7, 95% confidence interval 1.3-5.6) to be independently associated with disease recurrence. Conclusions: p21, p53, cyclin D1, and AURKA could possibly be used as prognostic markers to identify colon cancer patients with high risk of disease recurrence. © 2012 The Author(s).