Background: SPARC is a matricellular protein involved in tissue remodelling, cell migration and angiogenesis, while forkhead box P3 (FOXP3) protein functions as a transcription factor involved in immune cell regulation. Both SPARC and FOXP3 can play an anti-tumorigenic role in cancer progression. The aim was to determine if SPARC, FOXP3, CD8 and CD45RO expression levels are associated with colorectal cancer (CRC) stage, disease outcome and long-term cancer-specific survival (CSS) in stage II and III CRC. Methods and Findings: SPARC expression was initially assessed in 120 paired normal and stage I-IV CRCs. Subsequently, approximately 1000 paired patient samples of stage II or III CRCs in tissue microarrays were stained for SPARC, FOXP3, CD8 or CD45RO. Proportional hazards modelling assessed correlations between these markers and clinicopathological data, including disease outcome and cancer specific survival (CSS). Both SPARC and FOXP3 expression were significantly greater in CRC than normal colon (p<0.0001). High SPARC expression correlated with good disease outcome (≥60 mths without disease recurrence, p = 0.0039) and better long-term CSS in stage II CRC (<0.0001). In stage III CRC, high SPARC expression correlated with better long-term CSS (p<0.0001) and less adjuvant chemotherapy use (p = 0.01). High FOXP3 correlated with a good disease outcome, better long-term CSS and less adjuvant chemotherapy use in stage II (p<0.0037, <0.0001 and p = 0.04 respectively), but not in stage III CRC. High CD8 and CD45RO expression correlated with better disease outcome in stage II CRC, and better CSS, but the differences were not as marked as for SPARC and FOXP3. Conclusions: These data suggest that high SPARC and FOXP3 are associated with better disease outcome in stage II CRC and may be prognostic indicators of CSS. Further assessment of whether these markers predict patients at high risk of recurrence with stage II CRC and functional studies of these effects are underway.