Protein phosphorylation is a ubiquitous mechanism for cellular signal propagation, and signaling network complexity presents a challenge to protein kinase substrate identification. Few targets of Polo-like kinases are known, despite their significant role in coordinating cell-cycle progression. Here, we combine chemical-genetic, bioinformatic, and proteomic tools for Polo-like kinase substrate identification. Specific pharmacological inhibition of budding yeast Polo-like kinase, Cdc5, resulted in a misaligned preanaphase spindle and subsequently delayed anaphase nuclear migration, revealing a Cdc5 function. A cellular screen for Cdc5 substrates identified Spc72, a spindle pole body (SPB) component and microtubule anchor required for nuclear positioning. Spc72 bound to the Cdc5 PBD in a mitosis-specific manner, was phosphorylated by Cdc5 in vitro, and demonstrated a loss of mitotic phosphorylation in vivo upon Cdc5 inhibition. Finally, an examination of Cdc5 binding by SPB-localized proteins expanded our knowledge of Cdc5 function at the SPB.