Accurate division of cells into two daughters is a process that is vital to propagation of life. Protein phosphorylation and selective degradation have emerged as two important mechanisms safeguarding the delicate choreography of mitosis. Protein phosphatases catalyze dephosphorylation of thousands of sites on proteins, steering the cells through establishment of the mitotic phase and exit from it. A large E3 ubiquitin ligase, the anaphase-promoting complex/cyclosome (APC/C) becomes active during latter stages of mitosis through G1 and marks hundreds of proteins for destruction. Recent studies have revealed the complex interregulation between these two classes of enzymes. In this review, we highlight the direct and indirect mechanisms by which phosphatases and the APC/C mutually influence each other to ensure accurate spatiotemporal and orderly progression through mitosis, with a particular focus on recent insights and conceptual advances.