Most sporadic colorectal cancers are initiated by activating Wnt pathway mutations, characterized by the stabilization of beta-catenin and constitutive transcription by the beta-catenin/T cell factor-4 (Tcf-4) complex. EphB guidance receptors are Tcf4 target genes that control intestinal epithelial architecture through repulsive interactions with Ephrin-B ligands. Here we show that, although Wnt signalling remains constitutively active, most human colorectal cancers lose expression of EphB at the adenoma-carcinoma transition. Loss of EphB expression strongly correlates with degree of malignancy. Furthermore, reduction of EphB activity accelerates tumorigenesis in the colon and rectum of Apc(Min/+) mice, and results in the formation of aggressive adenocarcinomas. Our data demonstrate that loss of EphB expression represents a critical step in colorectal cancer progression.