Ferric uptake regulator (Fur) plays a key role in the iron homeostasis of prokaryotes, such as bacterial pathogens, but the molecular mechanisms and structural basis of Fur-DNA binding remain incompletely understood. Here, we report high-resolution structures of Magnetospirillum gryphiswaldense MSR-1 Fur in four different states: apo-Fur, holo-Fur, the Fur-feoAB1 operator complex and the Fur-Pseudomonas aeruginosa Fur box complex. Apo-Fur is a transition metal ion-independent dimer whose binding induces profound conformational changes and confers DNA-binding ability. Structural characterization, mutagenesis, biochemistry and in vivo data reveal that Fur recognizes DNA by using a combination of base readout through direct contacts in the major groove and shape readout through recognition of the minor-groove electrostatic potential by lysine. The resulting conformational plasticity enables Fur binding to diverse substrates. Our results provide insights into metal ion activation and substrate recognition by Fur that suggest pathways to engineer magnetotactic bacteria and antipathogenic drugs.