Archaeal histones and the eucaryal (eucaryotic) nucleosome core histones have almost identical histone folds. Here, we show that DNA molecules selectively incorporated by rHMfB (recombinant archaeal histone B from Methanothermus fervidus) into archaeal nucleosomes from a mixture of approximately 10(14) random sequence molecules contain sequence motifs shown previously to direct eucaryal nucleosome positioning. The dinucleotides GC, AA (=TT) and TA are repeated at approximately 10 bp intervals, with the GC harmonic displaced approximately 5 bp from the AA and TA harmonics [(GCN(3)AA or TA)(n)]. AT and CG were not strongly selected, indicating that TA not equalAT and GC not equalCG in terms of facilitating archaeal nucleosome assembly. The selected molecules have affinities for rHMfB ranging from approximately 9 to 18-fold higher than the level of affinity of the starting population, and direct the positioned assembly of archaeal nucleosomes. Fourier-transform analyses have revealed that AA dinucleotides are much enriched at approximately 10. 1 bp intervals, the helical repeat of DNA wrapped around a nucleosome, in the genomes of Eucarya and the histone-containing Euryarchaeota, but not in the genomes of Bacteria and Crenarchaeota, procaryotes that do not have histones. Facilitating histone packaging of genomic DNA has apparently therefore imposed constraints on genome sequence evolution, and since archaeal histones have no structure in addition to the histone fold, these constraints must result predominantly from histone fold-DNA contacts. Based on the three-domain universal phylogeny, histones and histone-dependent genome sequence evolution most likely evolved after the bacterial-archaeal divergence but before the archaeal-eucaryal divergence, and were subsequently lost in the Crenarchaeota. However, with lateral gene transfer, the first histone fold could alternatively have evolved after the archaeal-eucaryal divergence, early in either the euryarchaeal or eucaryal lineages.