Centromeres are epigenetically defined by the histone H3 variant, CENPA, which is crucial for faithful chromosome segregation and genome stability. CENP-A is distributed equally to sister chromatids during DNA replication in the S phase necessitating CENP-A replenishment in each round of the cell cycle. CENP-A deposition is initiated by the CENP-C-mediated targeting of the Mis18 complex (Mis18a, Mis18b, Mis18BP1) to the centromeres at mitotic exit. Subsequently, the Mis18 complex recruits the CENP-A assembly factor, HJURP, to deposit new CENP-A at the centromeres in early G1. HJURP interacts mainly with the Mis18ab C-terminal domains which are essential but not sufficient for HJURP binding. The Mis18 complex is targeted to the centromeres by direct interaction between Mis18BP1 and Mis18b with the C-terminal region of CENP-C to establish a robust centromeric association of the Mis18 complex. Furthermore, CDK and PLK1-mediated negative and positive regulation, respectively, restrict CENP-A deposition to early G1 in humans. CDK phosphorylation prevents the Mis18 complex assembly and centromeric targeting, while PLK1 directly binds and phosphorylates the Mis18 complex that is important for the centromeric association of the Mis18 complex and CENP-A deposition in early G1. Until today, several important aspects of the CENP-A maintenance pathway were discovered, however, mechanistic details of how the CENP-A deposition machinery is targeted to the centromeres are not fully understood. By using biochemical and mammalian cell-based techniques, this study demonstrates the molecular basis for HJURP/Mis18ab interaction and the implications for CENP-A deposition. Here, we demonstrate that Mis18ab MeDiY domains also contribute to HJURP binding and this implicates CENP-A deposition in vivo. Moreover, phosphorylation of the N-terminal region of Mis18a, potentially by PLK1, positively modulates HJURP/Mis18 complex interaction. Importantly, this study identified new interacting residues between HJURP and Mis18ab MeDiY and C-terminal domains. Finally, biochemical characterisation of CENP-C/Mis18b interaction in vitro showed a robust 2:1 complex formation. Mapping the minimum interaction region of the complex revealed a novel role for the highly conserved CENP-C motif, previously implicated in CENP-A binding, in mediating Mis18b interaction. Collectively, this study provides further insights into novel molecular interactions and regulatory mechanisms of the CENP-A deposition machinery that is essential for centromere maintenance.