We used comparative genomics to investigate the distribution of conserved DNA-binding motifs in the regulatory regions of genes involved in iron and manganese homeostasis in alpha-proteobacteria. Combined with other computational approaches, this allowed us to reconstruct the metal regulatory network in more than three dozen species with available genome sequences. We identified several classes of cis-acting regulatory DNA motifs (Irr-boxes or ICEs, RirA-boxes, Iron-Rhodo-boxes, Fur-alpha-boxes, Mur-box or MRS, MntR-box, and IscR-boxes) in regulatory regions of various genes involved in iron and manganese uptake, Fe-S and heme biosynthesis, iron storage, and usage. Despite the different nature of the iron regulons in selected lineages of alpha-proteobacteria, the overall regulatory network is consistent with, and confirmed by, many experimental observations. This study expands the range of genes involved in iron homeostasis and demonstrates considerable interconnection between iron-responsive regulatory systems. The detailed comparative and phylogenetic analyses of the regulatory systems allowed us to propose a theory about the possible evolution of Fe and Mn regulons in alpha-proteobacteria. The main evolutionary event likely occurred in the common ancestor of the Rhizobiales and Rhodobacterales, where the Fur protein switched to regulating manganese transporters (and hence Fur had become Mur). In these lineages, the role of global iron homeostasis was taken by RirA and Irr, two transcriptional regulators that act by sensing the physiological consequence of the metal availability rather than its concentration per se, and thus provide for more flexible regulation.