All eukaryotes contain centromere-specific histone H3 variants (CenH3s), which replace H3 in centromeric chromatin. We have previously documented the adaptive evolution of the Drosophila CenH3 (Cid) in comparisons of Drosophila melanogaster and Drosophila simulans, a divergence of approximately 2.5 million years. We have proposed that rapidly changing centromeric DNA may be driving CenH3's altered DNA-binding specificity. Here, we compare Cid sequences from a phylogenetically broader group of Drosophila species to suggest that Cid has been evolving adaptively for at least 25 million years. Our analysis also reveals conserved blocks not only in the histone-fold domain but also in the N-terminal tail. In several lineages, the N-terminal tail of Cid is characterized by subgroup-specific oligopeptide expansions. These expansions resemble minor groove DNA binding motifs found in various histone tails. Remarkably, similar oligopeptides are also found in N-terminal tails of human and mouse CenH3 (Cenp-A). The recurrent evolution of these motifs in CenH3 suggests a packaging function for the N-terminal tail, which results in a unique chromatin organization at the primary constriction, the cytological marker of centromeres.