In higher eukaryotes, the centromere is epigenetically specified by the histone H3 variant Centromere Protein-A (CENP-A). Deposition of CENP-A to the centromere requires histone chaperone HJURP (Holliday junction recognition protein). The crystal structure of an HJURP-CENP-A-histone H4 complex shows that HJURP binds a CENP-A-H4 heterodimer. The C-terminal β-sheet domain of HJURP caps the DNA-binding region of the histone heterodimer, preventing it from spontaneous association with DNA. Our analysis also revealed a novel site in CENP-A that distinguishes it from histone H3 in its ability to bind HJURP. These findings provide key information for specific recognition of CENP-A and mechanistic insights into the process of centromeric chromatin assembly.