Maintaining centromere identity relies upon the persistence of the epigenetic mark provided by the histone H3 variant, centromere protein A (CENP-A), but the molecular mechanisms that underlie its remarkable stability remain unclear. Here, we define the contributions of each of the three candidate CENP-A nucleosome-binding domains (two on CENP-C and one on CENP-N) to CENP-A stability using gene replacement and rapid protein degradation. Surprisingly, the most conserved domain, the CENP-C motif, is dispensable. Instead, the stability is conferred by the unfolded central domain of CENP-C and the folded N-terminal domain of CENP-N that becomes rigidified 1,000-fold upon crossbridging CENP-A and its adjacent nucleosomal DNA. Disrupting the 'arginine anchor' on CENP-C for the nucleosomal acidic patch disrupts the CENP-A nucleosome structural transition and removes CENP-A nucleosomes from centromeres. CENP-A nucleosome retention at centromeres requires a core centromeric nucleosome complex where CENP-C clamps down a stable nucleosome conformation and CENP-N fastens CENP-A to the DNA.