Iron (Fe) is a trace nutrient required by nearly all organisms. As a result of the demand for Fe and the toxicity of non-chelated cytosolic ionic Fe, regulatory systems have evolved to tightly balance Fe acquisition and usage while limiting overload. In most bacteria, including the mammalian pathogen Staphylococcus aureus, the ferric uptake regulator (Fur) is the primary transcriptional regulator that controls the transcription of genes that code for Fe uptake and utilization proteins. Fpa (formaly YlaN) was demonstrated to be essential in Bacillus subtilis unless excess Fe is added to the growth medium, suggesting a role in Fe homeostasis. Here, we demonstrate that Fpa is expendable in S. aureus; however, Fpa became essential upon Fe deprivation. A null fur allele bypassed the essentiality of Fpa. The absence of Fpa nearly abolished the derepression of Fur-dependent transcription during Fe limitation. Bioinformatic analyses suggest that fpa was recruited to Gram positive bacteria and once acquired was maintained in the genome as it co-evolved with Fur. Consistent with a role for Fpa in influencing Fur-dependent regulation, Fpa and Fur interacted in vivo and Fpa inhibits the DNA binding ability of Fur in vitro. Fpa bound Fe(II) in vitro using oxygen or nitrogen ligands with an association constant that is consistent with a physiological role in Fe sensing and/or buffering. These findings have led to a model wherein Fpa is an Fe(II) binding protein that influences Fur-dependent regulation through direct interaction.