Hfq regulates bacterial gene expression post-transcriptionally by binding small RNAs and their target mRNAs, facilitating sRNA-mRNA annealing, typically resulting in translation inhibition and RNA turnover. Hfq is also found in the nucleoid and binds double-stranded (ds) DNA with a slight preference for A-tracts. Here, we present the crystal structure of the Escherichia coli Hfq Core bound to a 30 bp DNA, containing three 6 bp A-tracts. Although previously postulated to bind to the 'distal' face, three statistically disordered double stranded DNA molecules bind across the proximal face of the Hfq hexamer as parallel, straight rods with B-DNA like conformational properties. One DNA duplex spans the diameter of the hexamer and passes over the uridine-binding proximal-face pore, whereas the remaining DNA duplexes interact with the rims and serve as bridges between adjacent hexamers. Binding is sequence-independent with residues N13, R16, R17 and Q41 interacting exclusively with the DNA backbone. Atomic force microscopy data support the sequence-independent nature of the Hfq-DNA interaction and a role for Hfq in DNA compaction and nucleoid architecture. Our structure and nucleic acid-binding studies also provide insight into the mechanism of sequence-independent binding of Hfq to dsRNA stems, a function that is critical for proper riboregulation.