The anaphase-promoting complex/cyclosome (APC/C) is a multisubunit E3 ligase required for ubiquitin-dependent proteolysis of cell-cycle-regulatory proteins, including mitotic cyclins and securin/Pds1. Regulation of APC/C activity and substrate recognition, mediated by the coactivators Cdc20 and Cdh1, is fundamental to cell-cycle control. However, the precise mechanism by which coactivators stimulate APC/C ubiquitylation activity and the nature of the substrate-binding sites on the activated APC/C are not understood. Here, we show that the optimal interaction of substrate with APC/C is dependent specifically on the simultaneous association of coactivator. This is consistent with a model whereby both core APC/C subunits and coactivators contribute recognition sites for substrates, accounting for the bipartite nature (D and KEN boxes) of most APC/C degradation signals. A direct and stoichiometric function for the coactivators could explain how specific substrates are recognized by APC/C in a cell-cycle-specific manner, and how coactivator stimulates APC/C ubiquitylation activity.