All eukaryotes organize their DNA in the form of nucleosomes, where an octamer of the four core histone proteins H2A, H2B, H3, and H4 wraps 147 base pairs of DNA wrapped in two tight superhelical turns. Histones are the targets of epigenetic modifications through the incorporation of histone variants and histone post-translational modifications, and require elaborate assembly and remodeling machinery for gene regulation. In contrast, many archaea organize their genomes with single, non-diversified histones that form slinkie-like structures, without the requirement for additional machinery to assemble and disassemble nucleosomal structures. A subclass of giant viruses (ancient DNA viruses that infect amoebae) also encode their own histones in the form of fused H4-H3 and H2B-H2A doublets, and these nucleosome-like structures are metastable and exhibit distinct features. Finally, I will describe how bacterial histones organize the bacterial nucleoid in a highly unusual manner. As such, histones are no longer a prerogative of eukaryotes but appear to be an ancient DNA packaging principle that has adapted to varying constraints in different domains of life.