Updated project metadata. Histones are the primary building blocks of chromatin in eukaryotes and many archaea. Bacteria are thought to rely on an orthogonal set of proteins to organize their chromosomes. Several bacterial genomes do, however, encode proteins with putative histone fold domains. Whether these proteins adopt a bona fide histone fold, assemble into higher order complexes that bind DNA, and play a central role in bacterial nucleoid physiology is not known. Here, we demonstrate that histones are major and essential building blocks of chromatin in the predatory bacterium Bdellovibrio bacteriovorus and the human pathogen Leptospira interrogans and likely important in several other bacterial clades. We determine the crystal structure of the B. bacteriovorus histone (Bd0055) dimer at 1.8Å resolution to reveal that histone fold topology, handshake dimer conformation, and the RD clamp motif are conserved between bacteria, archaea, and eukaryotes. However, ostensibly minor differences, including a shorter α2 helix, a less structured α3 helix, and a more acidic surface on one side of the dimer lead to a radically divergent DNA binding mode: instead of wrapping around the outer surface of a multi-subunit histone complex, DNA forms straight fibers, encased by a sheath of tightly packed Bd0055 dimers. Our results demonstrate that bacterial histones have evolved an atypical mode of DNA binding to become integral components of chromatin in distant parts of the bacterial kingdom.