Small basic proteins present in most Archaea share a common ancestor with the eukaryotic core histones. We report the crystal structure of an archaeal histone-DNA complex. DNA wraps around an extended polymer, formed by archaeal histone homodimers, in a quasi-continuous superhelix with the same geometry as DNA in the eukaryotic nucleosome. Substitutions of a conserved glycine at the interface of adjacent protein layers destabilize archaeal chromatin, reduce growth rate, and impair transcription regulation, confirming the biological importance of the polymeric structure. Our data establish that the histone-based mechanism of DNA compaction predates the nucleosome, illuminating the origin of the nucleosome.