The adenomatous polyposis coli (APC) tumor suppressor protein plays a critical role in regulating cellular levels of the oncogene product β-catenin. APC binds to β-catenin through a series of homologous 15 and 20 amino acid repeats. We have determined the crystal structure of a 15 amino acid β-catenin binding repeat from APC bound to the armadillo repeat region of β-catenin. Although it lacks significant sequence homology, the N-terminal half of the repeat binds in a manner similar to portions of E-cadherin and XTcf3, but the remaining interactions are unique to APC. We discuss the implications of this new structure for the design of therapeutics, and present evidence from structural, biochemical and sequence data, which suggest that the 20 amino acid repeats can adopt two modes of binding to β-catenin.