Heme, a physiologically crucial form of iron, is a cofactor for a very wide range of proteins and enzymes. These include DNA regulatory proteins in which heme is a sensor to which an analyte molecule binds, effecting a change in the DNA binding affinity of the regulator. Given that heme, and more generally iron, must be carefully regulated, it is surprising that there are no examples yet in bacteria in which heme itself is sensed directly by a reversibly binding DNA regulatory protein. Here we show that the Rhizobium leguminosarum global iron regulatory protein Irr, which has many homologues within the a-proteobacteria and is a member of the Fur superfamily, binds heme, resulting in a dramatic decrease in affinity between the protein and its cognate, regulatory DNA operator sequence. Spectroscopic studies of wild-type and mutant Irr showed that the principal (but not only) heme-binding site is at a conserved HXH motif, whose substitution led to loss of DNA binding in vitro and of regulatory function in vivo. The R. leguminosarum Irr behaves very differently to the Irr of Bradyrhizobium japonicum, which is rapidly degraded in vivo by an unknown mechanism in conditions of elevated iron or heme, but whose DNA binding affinity in vitro does not respond to heme.