The ubiquitylation of cell-cycle regulatory proteins by the large multimeric anaphase-promoting complex (APC/C) controls sister chromatid segregation and the exit from mitosis. Selection of APC/C targets is achieved through recognition of destruction motifs, predominantly the destruction (D)-box and KEN (Lys-Glu-Asn)-box. Although this process is known to involve a co-activator protein (either Cdc20 or Cdh1) together with core APC/C subunits, the structural basis for substrate recognition and ubiquitylation is not understood. Here we investigate budding yeast APC/C using single-particle electron microscopy and determine a cryo-electron microscopy map of APC/C in complex with the Cdh1 co-activator protein (APC/C(Cdh1)) bound to a D-box peptide at ∼10 Å resolution. We find that a combined catalytic and substrate-recognition module is located within the central cavity of the APC/C assembled from Cdh1, Apc10--a core APC/C subunit previously implicated in substrate recognition--and the cullin domain of Apc2. Cdh1 and Apc10, identified from difference maps, create a co-receptor for the D-box following repositioning of Cdh1 towards Apc10. Using NMR spectroscopy we demonstrate specific D-box-Apc10 interactions, consistent with a role for Apc10 in directly contributing towards D-box recognition by the APC/C(Cdh1) complex. Our results rationalize the contribution of both co-activator and core APC/C subunits to D-box recognition and provide a structural framework for understanding mechanisms of substrate recognition and catalysis by the APC/C.