To ensure the stable transmission of the genome during vertebrate cell division, the mitotic spindle must attach to a single locus on each chromosome, termed the centromere. The fundamental requirement for faithful centromere inheritance is the controlled deposition of the centromere-specifying histone, CENP-A. However, the regulatory mechanisms that ensure the precise control of CENP-A deposition have proven elusive. Here, we identify polo-like kinase 1 (Plk1) as a centromere-localized regulator required to initiate CENP-A deposition in human cells. We demonstrate that faithful CENP-A deposition requires integrated signals from Plk1 and cyclin-dependent kinase (CDK), with Plk1 promoting the localization of the key CENP-A deposition factor, the Mis18 complex, and CDK inhibiting Mis18 complex assembly. By bypassing these regulated steps, we uncoupled CENP-A deposition from cell-cycle progression, resulting in mitotic defects. Thus, CENP-A deposition is controlled by a two-step regulatory paradigm comprised of Plk1 and CDK that is crucial for genomic integrity.