Oxidative stress and iron limitation represent the grim side of life in an oxygen-rich atmosphere. The versatile electron transfer shuttle ferredoxin, an iron-sulfur protein, is particularly sensitive to these hardships, and its downregulation under adverse conditions severely compromises survival of phototrophs. Replacement of ferredoxin by a stress-resistant isofunctional carrier, flavin-containing flavodoxin, is a widespread strategy employed by photosynthetic microorganisms to overcome environmental adversities. The flavodoxin gene was lost in the course of plant evolution, but its reintroduction in transgenic plants confers increased tolerance to environmental stress and iron starvation, raising the question as to why a genetic asset with obvious adaptive value was not kept by natural selection. Phylogenetic analyses reveal that the evolutionary history of flavodoxin is intricate, with several horizontal gene transfer events between distant organisms, including Eukarya, Bacteria, and Archaea. The flavodoxin gene is unevenly distributed in most algal lineages, with flavodoxin-containing species being overrepresented in iron-limited regions and scarce or absent in iron-rich environments. Evaluation of cyanobacterial genomic and metagenomic data yielded essentially the same results, indicating that there was little selection pressure to retain flavodoxin in iron-rich coastal/freshwater phototrophs. Our results show a highly dynamic evolution pattern of flavodoxin tightly connected to the bioavailability of iron. Evidence presented here also indicates that the high concentration of iron in coastal and freshwater habitats may have facilitated the loss of flavodoxin in the freshwater ancestor of modern plants during the transition of photosynthetic organisms from the open oceans to the firm land.