Eukaryotic cells rely on a surveillance mechanism known as the spindle checkpoint to ensure accurate chromosome segregation. The spindle checkpoint prevents sister chromatids from separating until all kinetochores achieve bipolar attachments to the mitotic spindle^,,. Checkpoint proteins tightly inhibit the anaphase-promoting complex (APC), a ubiquitin ligase required for chromosome segregation and progression to anaphase. Unattached kinetochores promote the binding of checkpoint proteins Mad2 and BubR1 to the APC-activator Cdc20, rendering it unable to activate APC. Once all kinetochores are properly attached, however, cells inactivate the checkpoint within minutes, allowing for the rapid and synchronous segregation of chromosomes. How cells switch from strong APC inhibition before kinetochore attachment to rapid APC activation once attachment is complete remains a mystery. Here we show that checkpoint inactivation is an energy-consuming process involving APC-dependent multi-ubiquitination. Multi-ubiquitination by APC leads to the dissociation of Mad2 and BubR1 from Cdc20, a process that is reversed by a Cdc20-directed de-ubiquitinating enzyme. The mutual regulation between checkpoint proteins and APC leaves the cell poised for rapid checkpoint inactivation and ensures that chromosome segregation promptly follows the completion of kinetochore attachment. In addition, our results suggest a mechanistic basis for how cancer cells can have a compromised spindle checkpoint without corresponding mutations in checkpoint genes.