Polo-like kinase (Plk1) is crucial for cell cycle progression through mitosis. Here we present the molecular and structural mechanisms that regulate the substrate recognition of Plk1 and influence its centrosomal localization and activity. Our work shows that Plk1 localization is controlled not only by the polo box domain (PBD); remarkably, the kinase domain is also involved in Plk1 targeting mechanism to the centrosome. The crystal structures of the PBD in complex with Cdc25C and Cdc25C-P target peptides reveal that Trp-414 is fundamental in their recognition regardless of its phosphorylation status. Binding measurements demonstrate that W414F mutation abolishes molecular recognition and diminishes centrosomal localization. Therefore, Plk1 centrosomal localization is not controlled by His-538 and Lys-540, the residues involved in phosphorylated target binding. The different conformations of the loop, which connects the polo boxes in the apo and the PBD-Cdc25C and PBD-Cdc25C-P complex structures, together with changes in the proline adjacent to the phosphothreonine in the target peptide, suggest a regulatory mechanism to detect binding of unphosphorylated or phosphorylated target substrates. Altogether, these data propose a model for the interaction between Plk1 and Cdc25C.