Polo-like kinase 1 (Plk1) is an essential protein kinase that promotes faithful mitotic progression in eukaryotes. Plk1 subcellular localization and substrate interactions are tightly controlled and require binding of Plk1 to phosphorylated sequences. Here, we use quantitative proteomics to identify phosphorylation-dependent interactions within the Plk1 network in human mitotic HeLa cells using kinase inhibitors and a Plk1 mutant deficient in phosphorylation-dependent substrate binding. We find that many interactions are abolished upon kinase inhibition; however, a subset are protected from phosphatase opposition or are unopposed, resulting in persistent Plk1-substrate interactions. This subset includes Phosphoprotein Phosphatase 6 (PP6), whose activity towards Aurora kinase A (AURKA) is inhibited by Plk1. This Plk1-PP6 interaction creates a feedback loop that coordinates and reinforces the activities of Plk1 and AURKA during mitotic entry and is terminated by Plk1 degradation during mitotic exit. Collectively, this work provides a cellular mechanism for the observed regulation of AURKA by Plk1.