Muscarinic acetylcholine receptor M3 (M3R) has repeatedly been shown to be prominently expressed in human colorectal cancer (CRC), playing roles in proliferation and cell invasion. Its therapeutic targetability has been suggested in vitro and in animal models. We aimed to investigate the clinical role of MR3 expression in CRC for human survival. Surgical tissue samples from 754 CRC patients were analyzed for high or low immunohistochemical M3R expression on a clinically annotated tissue microarray (TMA). Immunohistochemical analysis was performed for established immune cell markers (CD8, TIA-1, FOXP3, IL 17, CD16 and OX 40). We used Kaplan–Meier curves to evaluate patients’ survival and multivariate Cox regression analysis to evaluate prognostic significance. High M3R expression was associated with increased survival in multivariate (hazard ratio (HR) = 0.52; 95% CI = 0.35–0.78; p = 0.001) analysis, as was TIA-1 expression (HR = 0.99; 95% CI = 0.94–0.99; p = 0.014). Tumors with high M3R expression were significantly more likely to be grade 2 compared to tumors with low M3R expression (85.7% vs. 67.1%, p = 0.002). The 5-year survival analysis showed a trend of a higher survival rate in patients with high M3R expression (46%) than patients with low M3R expression CRC (42%) (p = 0.073). In contrast to previous in vitro and animal model findings, this study demonstrates an increased survival for CRC patients with high M3R expression. This evidence is highly relevant for translation of basic research findings into clinically efficient treatments.