Background: BolA and glutaredoxin interact together in the iron metabolism. Results: They form two types of heterodimers with different binding surfaces depending on the presence or absence of an iron-sulfur cluster. Conclusion: The function of both proteins is likely modulated by the nature of the interaction. Significance: Understanding the molecular mechanisms responsible for iron sensing is crucial for all iron-mediated cellular processes. BolA proteins are defined as stress-responsive transcriptional regulators, but they also participate in iron metabolism. Although they can form [2Fe-2S]-containing complexes with monothiol glutaredoxins (Grx), structural details are lacking. Three Arabidopsis thaliana BolA structures were solved. They differ primarily by the size of a loop referred to as the variable [H/C] loop, which contains an important cysteine (BolA_C group) or histidine (BolA_H group) residue. From three-dimensional modeling and spectroscopic analyses of A. thaliana GrxS14-BolA1 holo-heterodimer (BolA_H), we provide evidence for the coordination of a Rieske-type [2Fe-2S] cluster. For BolA_C members, the cysteine could replace the histidine as a ligand. NMR interaction experiments using apoproteins indicate that a completely different heterodimer was formed involving the nucleic acid binding site of BolA and the C-terminal tail of Grx. The possible biological importance of these complexes is discussed considering the physiological functions previously assigned to BolA and to Grx-BolA or Grx-Grx complexes.