The ability to utilize the siderophore ferrichrome as an iron source was found to be a variable trait in a field population of mesorhizobia. To investigate the genetic basis of this variation, genes required for ferrichrome utilization (fhu genes) were characterized in Mesorhizobium strain R88B, an Fhu+ member of the population. Functional fhu genes were present at three loci. Two genes of the ferrichrome ABC transporter, fhuBD, were identified at an fhu1 locus downstream of the symbiosis island that was integrated at the phe-tRNA gene. The fhuA gene encoding the ferrichrome outer membrane receptor was located in the fhu2 locus together with non-functional fhuDB genes, while the fhuC gene encoding the ATPase required for ferrichrome transport was part of the fhu3 locus that included genes required to form a functional TonB complex. None of the fhu genes were present in the sequenced Mesorhizobium loti strain MAFF303099. Comparisons with MAFF303099 suggested that the fhu2 and fhu3 loci evolved through small-scale (< 5 kb) acquisitions and deletions. Despite their independent origins, the three fhu loci were coordinately regulated in response to iron availability. Within the mesorhizobial population, the ability to utilize ferrichrome was most strongly correlated with the presence of the fhuA gene. We hypothesize that the ferrichrome transport system evolved through cycles of gene acquisition and deletion, with the positive selection pressure of an iron-poor or siderophore-rich environment being offset by the negative pressure of the outer membrane receptor being a target for phage.