The tumor suppressor APC protein associates with the cadherin-binding proteins alpha- and beta-catenin. To examine the relationship between cadherin, catenins, and APC, we have tested combinatorial protein-protein interactions in vivo, using a yeast two-hybrid system, and in vitro, using purified proteins. beta-Catenin directly binds to APC at high and low affinity sites. alpha-Catenin cannot directly bind APC but associates with it by binding to beta-catenin. Plakoglobin, also known as gamma-catenin, directly binds to both APC and alpha-catenin and also to the APC-beta-catenin complex, but not directly to beta-catenin. beta-Catenin binds to multiple independent regions of APC, some of which include a previously identified consensus motif and others which contain the centrally located 20 amino acid repeat sequences. The APC binding site on beta-catenin may be discontinuous since neither the carboxyl- nor amino-terminal halves of beta-catenin will independently associate with APC, although the amino-terminal half independently binds alpha-catenin. The catenins bind to APC and E-cadherin in a similar fashion, but APC and E-cadherin do not associate with each other either in the presence or absence of catenins. Thus, APC forms distinct heteromeric complexes containing combinations of alpha-catenin, beta-catenin, and plakoglobin which are independent from the cadherin-catenin complexes.