The adenomatous polyposis coli (APC) tumor suppressor forms a complex with Axin and GSK3β to promote the phosphorylation and degradation of β-catenin, a key co-activator of Wnt-induced transcription. Here, we establish that APC is modified predominantly with K63-linked ubiquitin chains when it is bound to Axin in unstimulated HEK293 cells. Wnt3a stimulation induced a time-dependent loss of K63-polyubiquitin adducts from APC, an effect synchronous with the dissociation of Axin from APC and the stabilization of cytosolic β-catenin. RNAi-mediated depletion of Axin or β-catenin, which negated the association between APC and Axin, resulted in the absence of K63-adducts on APC. Overexpression of wild-type and phosphodegron-mutant β-catenin, combined with analysis of thirteen human cancer cell lines that harbor oncogenic mutations in APC, Axin, or β-catenin, support the hypothesis that a fully assembled APC-Axin-GSK3β-phospho-β-catenin complex is necessary for the K63-polyubiquitylation of APC. Intriguingly, the degree of this modification on APC appears to correlate inversely with the levels of β-catenin in cells. Together, our results indicate that K63-linked polyubiquitin adducts on APC regulate the assembly and/or efficiency of the β-catenin destruction complex.