Adenomatous polyposis coli (APC) regulates cell-cell adhesion and cell migration through activating the APC-stimulated guanine nucleotide-exchange factor (GEF; Asef), which is usually autoinhibited through the binding between its Src homology 3 (SH3) and Dbl homology (DH) domains. The APC-activated Asef stimulates the small GTPase Cdc42, which leads to decreased cell-cell adherence and enhanced cell migration. In colorectal cancers, truncated APC constitutively activates Asef and promotes cancer cell migration and angiogenesis. Here, we report crystal structures of the human APC/Asef complex. We find that the armadillo repeat domain of APC uses a highly conserved surface groove to recognize the APC-binding region (ABR) of Asef, conformation of which changes dramatically upon binding to APC. Key residues on APC and Asef for the complex formation were mutated and their importance was demonstrated by binding and activity assays. Structural superimposition of the APC/Asef complex with autoinhibited Asef suggests that the binding between APC and Asef might create a steric clash between Asef-DH domain and APC, which possibly leads to a conformational change in Asef that stimulates its GEF activity. Our structures thus elucidate the molecular mechanism of Asef recognition by APC, as well as provide a potential target for pharmaceutical intervention against cancers.