The E6AP ubiquitin ligase catalyzes the high-risk human papillomaviruses' E6-mediated ubiquitylation of p53, contributing to the neoplastic progression of cells infected by these viruses. Defects in the activity and the dosage of E6AP are linked to Angelman syndrome and to autism spectrum disorders, respectively, highlighting the need for precise control of the enzyme. With the exception of HERC2, which modulates the ubiquitin ligase activity of E6AP, little is known about the regulation or function of E6AP normally. Using a proteomic approach, we have identified and validated several new E6AP-interacting proteins, including HIF1AN, NEURL4, and mitogen-activated protein kinase 6 (MAPK6). E6AP exists as part of several different protein complexes, including the proteasome and an independent high-molecular-weight complex containing HERC2, NEURL4, and MAPK6. In examining the functional consequence of its interaction with the proteasome, we found that UBE3C (another proteasome-associated ubiquitin ligase), but not E6AP, contributes to proteasomal processivity in mammalian cells. We also found that E6 associates with the HERC2-containing high-molecular-weight complex through its binding to E6AP. These proteomic studies reveal a level of complexity for E6AP that has not been previously appreciated and identify a number of new cellular proteins through which E6AP may be regulated or functioning.