The conserved Polo kinase controls multiple events in mitosis and cytokinesis. Although Polo-like kinases are regulated by phosphorylation and proteolysis, control of subcellular localization plays a major role in coordinating their mitotic functions. This is achieved largely by the Polo-Box Domain, which binds prephosphorylated targets. However, it remains unclear whether and how Polo might interact with partner proteins when priming mitotic kinases are inactive. Here we show that Polo associates with microtubules in interphase and cytokinesis, through a strong interaction with the microtubule-associated protein Map205. Surprisingly, this interaction does not require priming phosphorylation of Map205, and the Polo-Box Domain of Polo is required but not sufficient for this interaction. Moreover, phosphorylation of Map205 at a CDK site relieves this interaction. Map205 can stabilize Polo and inhibit its cellular activity in vivo. In syncytial embryos, the centrosome defects observed in polo hypomorphs are enhanced by overexpression of Map205 and suppressed by its deletion. We propose that Map205-dependent targeting of Polo to microtubules provides a stable reservoir of Polo that can be rapidly mobilized by the activity of Cdk1 at mitotic entry.