The anaphase-promoting complex (APC), or cyclosome, is an E3 ubiquitin-protein ligase that collaborates with E2 ubiquitin-conjugating enzymes to assemble polyubiquitin chains on proteins important for cell-cycle progression. It remains unclear how the APC - or many other E3s - promotes the multiple distinct reactions necessary for chain assembly. We addressed this problem by analyzing APC interactions with different E2s. We screened all budding yeast E2s as APC coenzymes in vitro and found that two, Ubc4 and Ubc1, are the key E2 partners for the APC. These proteins display strikingly different but complementary enzymatic behaviors: Ubc4 supports the rapid monoubiquitination of multiple lysines on APC targets, while Ubc1 catalyzes K48-linked polyubiquitin chain assembly on preattached ubiquitins. Mitotic APC function is lost in yeast strains lacking both Ubc1 and Ubc4. E2-25K, a human homolog of Ubc1, also promotes APC-dependent chain extension on preattached ubiquitins. We propose that sequential E2 proteins catalyze K48-linked polyubiquitination and thus proteasomal destruction of APC targets.